Chomsky 文法分类体系

0 型文法（Type-0 Grammar）

$\alpha\to \beta$

无限制文法（Unrestricted Grammar）/ 短语结构文法（Phrase Structure Grammar, PSG）

$\forall \alpha \to \beta \in P , \alpha$ 中至少包含 1 个非终结符

0 型语言：由 0 型文法 $G$ 生成的语言 $L(G)$

1 型文法（Type-1 Grammar）

$\alpha\to \beta$

上下文有关文法（Context-Sensitive Grammar, CSG）

$\forall \alpha\to \beta \in P, |\alpha| \le |\beta|$

产生式的一般形式： $\alpha_1 A \alpha_2 \to \alpha_1 \beta \alpha_2 \quad (\beta \ne \varepsilon)$

• （CSG 中不包括 $\varepsilon$-产生式）

上下文有关语言（1型语言）：由上下文有关文法 $G$ 生成的语言 $L(G)$

2 型文法（Type-2 Grammar）

$\alpha\to \beta$

上下文无关文法（Context-Free Grammar, CFG）

$\forall \alpha \to \beta\in P, \alpha \in$ $V_N$

产生式的一般形式：$A\to \beta$

• e.g.

上下文无关语言（2型语言）：由上下文无关文法 $G$ 生成的语言 $L(G)$

3 型文法（Type-3 Grammar）

$\alpha\to \beta$

正则文法（Regular Grammar, RG）

右线性（Right Linear）文法： $A\to wB$ 或 $A\to w$

左线性（Left Linear）文法： $A\to Bw$ 或 $A\to w$

左线性文法和右线性文法都称为正则文法

• e.g. ⭐

正则语言（3型语言）：由正则文法 $G$ 生成的语言 $L(G)$

正则文法能够描述程序设计语言的多数单词。