Chomsky分类法

$$G=(V,T,P,S)$$

是一个文法。

0 型文法

产生式形如 $\alpha \to \beta$，其中 $\alpha ,\beta \in (V\cup T{)}^{\ast }$ 且 $\alpha$ 中至少有一个非终结符。 能力相当于图灵机。

1 型文法

上下文有关文法，产生式形如 $\alpha \to \beta$，$|\alpha |\le |\beta |$，仅有 $S\to ϵ$ 例外，且 $S$ 不能出现在产生式右侧。 能力相当于线性有界自动机。

2 型文法

上下文无关文法，产生式形如 $\alpha \to \beta$，$\alpha \in V,\beta \in (V\cup T{)}^{\ast }$。 能力相当于下推自动机。

3 型文法

正规文法，产生式形如 $A\to aB或A\to a$，其中 $A,B\in V,a\in T\cup \left\{ϵ\right\}$。 能力相当于有限状态自动机。