乔姆斯基语法分类

根据诺姆·乔莫斯基的说法，语法有四种类型 −类型 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 语法 生成递归可枚举语言。产生式没有限制。它们是任何相结构语法，包括所有形式语法。

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

产生式可以采用 α → β 的形式，其中 α 是包含至少一个非终端的终端和非终端字符串，并且 α 不能为空。β 是包含终端和非终端的字符串。

示例

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