乔姆斯基谱系

乔姆斯基谱系表示被不同机器接受的语言类别。乔姆斯基谱系中语言的类别如下

1. 类型 0 称为无限制语法。
2. 类型 1 称为上下文敏感语法。
3. 类型 2 称为上下文无关语法。
4. 类型 3 正则语法。

这是一个谱系。因此，类型 3 的每种语言也属于类型 2、1 和 0。类似地，类型 2 的每种语言也属于类型 1 和类型 0 等。

类型 0 语法

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

例如

类型 1 语法

类型 1 语法被称为上下文敏感语法。 上下文敏感语法用于表示上下文敏感语言。 上下文敏感语法遵循以下规则

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

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

例如

类型 2 语法

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

其中 A 是任何单个非终结符， 是终结符和非终结符的任何组合。

例如

类型 3 语法

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

类型 3 是最受限制的语法形式。 类型 3 语法应该是类型 2 和类型 1。 类型 3 应该采用以下形式

例如