喬姆斯基文法分類



根據諾姆·喬姆斯基的理論,共有四種類型的文法:0型、1型、2型和3型。下表顯示了它們之間的區別:

文法型別 被接受的文法 被接受的語言 自動機

0型 無限制文法 遞迴可列舉語言 圖靈機
1型 上下文有關文法 上下文有關語言 線性有界自動機
2型 上下文無關文法 上下文無關語言 下推自動機
3型 正則文法 正則語言 有限狀態自動機

請看下圖,它顯示了每種文法的範圍:

Containment of Type3, Type2, Type1, Type0

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 
廣告