乔姆斯基语法分类

---

根据诺姆·乔莫斯基 (Noam Chomosky) 的说法，语法有四种类型 - 类型 0、类型 1、类型 2 和类型 3。下表显示了它们之间的区别 -

看看下面的插图。它显示了每种语法类型的范围 -

类型 - 3 语法

Type-3 语法生成常规语言。类型 3 语法必须在左侧有一个非终结符，右侧必须包含一个终结符或单个终结符后跟一个非终结符。

产品必须采用X → a 或 X → aY 的形式

其中X, Y ∈ N（非终结符）

和a ∈ T（终端）

如果S没有出现在任何规则的右侧，则规则S → ε是允许的。

例子

X → ε 
X → a | aY
Y → b 

类型 - 2 语法

Type-2 语法生成上下文无关语言。

产生式必须采用A → γ的形式

其中A ∈ N（非终结符）

和γ ∈ (T ∪ N)*（终结符和非终结符串）。

由这些语法生成的这些语言由非确定性下推自动机识别。

例子

S → X a 
X → a 
X → aX 
X → abc 
X → ε

类型 - 1 语法

Type-1 语法生成上下文相关语言。作品必须采用以下形式

α A β → α γ β

其中A ∈ N（非终结符）

和α, β, γ ∈ (T ∪ N)*（终结符和非终结符串）

字符串α和β可以为空，但γ必须非空。

如果 S 没有出现在任何规则的右侧，则规则S → ε是允许的。这些语法生成的语言由线性有界自动机识别。

例子

AB → AbBc 
A → bcA 
B → b 

类型 - 0 语法

Type-0 语法生成递归可枚举语言。制作没有任何限制。它们是任何阶段结构语法，包括所有形式语法。

它们生成图灵机可以识别的语言。

产品可以采用α → β的形式，其中α是一串终结符和非终结符，其中至少有一个非终结符，并且α不能为空。β是一串终结符和非终结符。

例子

S → ACaB 
Bc → acB 
CB → DB 
aD → Db