Automata Theory 简明教程

q4 生成正则语言。Type-3 语法必须在左侧有一个非终结符，在右侧有一个终结符或一个终结符后跟一个非终结符。

产生式必须采用以下形式 Type-3 grammars

其中 X → a or X → aY （非终结符）

和 X, Y ∈ N （终结符）

规则 a ∈ T 被允许，如果 S → ε 不出现在任何规则的右侧。

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

产生式应为 A → γ 形式

其中*A ∈ N*（非终结符）

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

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

Type-1 grammars 生成上下文相关语言。产生式应为

α A β → α γ β

其中 A ∈ N （非终结符）

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

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

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

Type-0 grammars 递归生成可枚举的语言。产生式没有任何限制。它们是包括所有形式文法的任意相结构语法。

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

产生式可以 α → β 的形式出现，其中 α 是至少有一个非终结符的终结符和非终结符字符串，而 α 不能为 null。 β 是终结符和非终结符字符串。