自动机Chomsky层次结构

Chomsky层次结构表示不同机器接受的语言类别。乔姆斯基层次结构中的语言类别如下：

1. 类型0称为无限制语法。
2. 类型1称为上下文相关语法。
3. 类型2称为上下文无关语法。
4. 类型3常规语法。

这是一个层次结构。因此，类型3的每种语言也都是类型2、1和0。类似地，类型2的每种语言也都是类型1和类型0，依此类推。

类型0语法：

类型0语法称为无限制语法。这些类型的语言的语法规则没有限制。这些语言可以由图灵机有效地建模。

例如：

bAa → aa
S → s

类型1语法：

类型1语法称为上下文相关语法。上下文相关的语法用于表示上下文相关的语言。上下文相关的语法遵循以下规则：

• 上下文相关的语法在其生产规则的左侧可能有多个符号。
• 左侧的符号数量不得超过右侧的符号数量。
• 除非A是起始符号，否则不允许采用A→ε形式的规则。它不会出现在任何规则的右侧。
• 类型1的语法应为类型0。在类型1中，产生形式为V→T

V中的符号计数小于或等于T的情况。

例如：

S → AT
T → xy
A → a

类型2语法：

类型2语法称为上下文无关语法。上下文无关语言是可以由上下文无关文法（CFG）表示的语言。类型2应该为类型1。生产规则的格式为

A → α

其中A是任何单个非末端，并且是末端和非末端的任何组合。

例如：

A → aBb
A → b
B → a

类型3语法：

类型3语法被称为常规语法。正则语言是可以使用正则表达式描述的语言。可以使用NFA或DFA对这些语言进行建模。

类型3是语法的最受限制形式。类型3语法应为类型2和类型1。类型3的形式应为

V → T*V / T*

例如：

A → xy