Automata Theory 简明教程
Chomsky Normal Form
如果产生式满足以下形式，则一个 CFG 处于乔姆斯基范式−
-
A → a
-
A → BC
-
S → ε
其中 A、B 和 C 是非终结符，而 a 是终结符。
Algorithm to Convert into Chomsky Normal Form −
Step 1 − 如果起始符号 S 出现在某个右侧，创建一个新的起始符号 S’ 和一个新的产生式 S’→ S 。
Step 2 − 删除空产生式。（使用前面讨论的空产生式消除算法）
Step 3 − 删除单位产生式。（使用前面讨论的单位产生式消除算法）
Step 4 − 替换每个将 n > 2 替换成 A → B1C 产生的 A → B1…Bn ，将 C → B2 …Bn 替换成 A → B1C 。对右侧有两个或更多符号的每个产生式重复此步骤。
Step 5 − 如果任何产生式的右侧形式为 A → aB ，其中 a 是一个终结符且 A, B 是非终结符，那么该产生式被替换为 A → XB 和 X → a 。对形式为 A → aB 的每个产生式重复此步骤。
Solution
(1) 因为 S 出现在 R.H.S 中，我们添加一个新状态 S0 ， S0→S 被添加到产生式集中并变为 −
S0→S, S→ ASA | aB, A → B | S, B → b | ∈
(2) 现在我们将删除空发生式 −
B → ∈和 A → ∈
在删除了 B → ε 后，产生式集变为 −
S0→S, S→ ASA | aB | a, A → B | S | ∈, B → b
在删除了 A → ∈ 后，产生式集变为 −
S0→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b
(3) 现在我们将删除单元产生式。
在删除了 S → S 后，产生式集变为 −
S0→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b
在删除了 S0→ S 后，产生式集变为 −
S0→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A → B | S, B → b
在删除了 A→ B 后，产生式集变为 −
S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A → S | b
B→b
移除 A→S 后，产生式集合变为 −
S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A→b |ASA | aB | a | AS | SA，B→b
(4) 现在我们将寻找 R.H.S 中有多个变量的项
此处，S0→ASA、S→ASA、A→ASA 违反了 R.H.S 中的两个非终结符。
因此，我们将应用步骤 4 和步骤 5 来获得以下在 CNF 中的最终产生式集合 −
S0→AX | aB | a | AS | SA
S→AX | aB | a | AS | SA
A→b |AX | aB | a | AS | SA
B→b
X→SA
(5) 我们必须更改产生式 S0→aB、S→aB、A→aB
最终产生式集合变为 −
S0→AX | YB | a | AS | SA
S→AX | YB | a | AS | SA
A→b A→b |AX | YB | a | AS | SA
B→b
X→SA
Y→a