Chomsky 范式

阐述

即上下文无关文法的每个规则是以下的一种：

• $A\to BC$（其中 $B,C\ne S$）
• $A\to a$
• $S\to\varepsilon$

实例

性质

相关内容

可以将任意CFG转化为这种范式：

1. 添加一个新的起始变量
2. 去掉形如 $A\to\varepsilon$ 的规则，并对所有 $R\to uAv$ 的规则添加一条 $A$ 替换为空的规则
3. 去掉形如 $A\to B$ 的规则，并对所有 $B\to u$ 的规则添加一条 $A\to u$ 的规则
4. 将形如 $A\to u_1u_2...$ 的规则拆分成多条
   1. $A\to u_1A_1, A_1\to u_2A_2,\cdots,A_{k-2}\to u_{k-1}u_k$
   2. 如果原本 $u_i$ 是终结符，替换并添加 $U_i\to u_i$

参考文献