阿摩線上測驗
二、諾姆·荷姆斯基（Noam Chomosky）定義了 type-0、type-1、type-2、type-3 四種語法類型，請說明各類型可接受之語言（Language Accepted）是什 麼？相對應之自動機（Automaton）是什麼？（20 分）
詳解 (共 1 筆)
詳解
| 語法類型 | 可接受之語言 | 相對應之自動機 |
|---|---|---|
| Type-0 | 圖靈可計算語言 | 圖靈機 |
| Type-1 | 上下文相關語言 | 線性有界自動機 |
| Type-2 | 上下文無關語言 | 下推自動機 |
| Type-3 | 正規語言 | 有限狀態機 |
這些語法類型和相應的自動機模型構成了形式語言和自動機理論的基礎，用於理解計算的理論極限和語言的結構。