
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- 穆爾機與米利機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的閉包性質
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 由 CFG 構造 PDA
- 下推自動機和語法分析
- 圖靈機
- 圖靈機 (TM) 基礎知識
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性有界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
喬姆斯基文法分類
根據諾姆·喬姆斯基的理論,共有四種類型的文法:0型、1型、2型和3型。下表顯示了它們之間的區別:
文法型別 | 被接受的文法 | 被接受的語言 | 自動機 |
---|---|---|---|
0型 | 無限制文法 | 遞迴可列舉語言 | 圖靈機 |
1型 | 上下文有關文法 | 上下文有關語言 | 線性有界自動機 |
2型 | 上下文無關文法 | 上下文無關語言 | 下推自動機 |
3型 | 正則文法 | 正則語言 | 有限狀態自動機 |
請看下圖,它顯示了每種文法的範圍:

3型文法
3型文法生成正則語言。3型文法的左邊必須只有一個非終結符,右邊由單個終結符或單個終結符後跟單個非終結符組成。
產生式必須是X → a 或 X → aY的形式
其中X, Y ∈ N(非終結符)
且a ∈ T(終結符)
如果S不出現在任何規則的右側,則允許規則S → ε。
示例
X → ε X → a | aY Y → b
2型文法
2型文法生成上下文無關語言。
產生式必須是A → γ的形式
其中A ∈ N(非終結符)
且γ ∈ (T ∪ N)*(終結符和非終結符的字串)。
這些文法生成的語言可以被非確定性下推自動機識別。
示例
S → X a X → a X → aX X → abc X → ε
1型文法
1型文法生成上下文有關語言。產生式必須是
α A β → α γ β
的形式,其中A ∈ N(非終結符)
且α, β, γ ∈ (T ∪ N)*(終結符和非終結符的字串)
字串α和β可以為空,但γ不能為空。
如果 S不出現在任何規則的右側,則允許規則S → ε。這些文法生成的語言可以被線性有界自動機識別。
示例
AB → AbBc A → bcA B → b
0型文法
0型文法生成遞迴可列舉語言。產生式沒有限制。它們是任何短語結構文法,包括所有形式文法。
它們生成的語言可以被圖靈機識別。
產生式可以是α → β的形式,其中α是至少包含一個非終結符的終結符和非終結符的字串,並且α不能為null。β是終結符和非終結符的字串。
示例
S → ACaB Bc → acB CB → DB aD → Db
廣告