乔姆斯基范式
如果产生式符合以下形式 −，则 CFG 符合乔姆斯基范式
- A → a
- A → BC
- S → ε
其中 A、B 和 C 为非终结符，而 a 为终结符。
转换为乔姆斯基范式 − 的算法
步骤 1 − 如果起始符号 S 出现在右侧，则创建新的起始符号 S' 和新的产生式 S'→ S。
步骤 2 − 删除空产生式。 （使用前面讨论过的空产生式移除算法）
步骤 3 − 移除单位产生式。（使用前面讨论过的单位产生式移除算法）
步骤 4 − 将每个产生式 A → B1…Bn 其中 n > 2 替换为 A → B1C 其中 C → B2 …Bn。对右侧有两个或更多符号的所有产生式重复此步骤。
步骤 5 − 如果任何产生式的右侧形式为 A → aB 其中 a 是终端而 A, B 是非终端，则产生式将替换为 A → XB 和 X → a。对每个形式为 A → aB 的产生式重复此步骤。
问题
将以下 CFG 转换为 CNF
S → ASA | aB, A → B | S, B → b | ε
解决方案
(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
