Chomsky层次结构表示不同机器接受的语言类别。乔姆斯基层次结构中的语言类别如下：
- 类型0称为无限制语法。
- 类型1称为上下文相关语法。
- 类型2称为上下文无关语法。
- 类型3常规语法。
文章图片
【自动机Chomsky层次结构】这是一个层次结构。因此，类型3的每种语言也都是类型2、1和0。类似地，类型2的每种语言也都是类型1和类型0，依此类推。
类型0语法：
类型0语法称为无限制语法。这些类型的语言的语法规则没有限制。这些语言可以由图灵机有效地建模。
例如：
bAa → aa
S → s类型1语法：
类型1语法称为上下文相关语法。上下文相关的语法用于表示上下文相关的语言。上下文相关的语法遵循以下规则：
- 上下文相关的语法在其生产规则的左侧可能有多个符号。
- 左侧的符号数量不得超过右侧的符号数量。
- 除非A是起始符号，否则不允许采用A→ε形式的规则。它不会出现在任何规则的右侧。
- 类型1的语法应为类型0。在类型1中，产生形式为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
