乔姆斯基文法分类

---

---

根据诺姆·乔姆斯基的理论，共有四种类型的文法：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