grammar - 将语法转换为乔姆斯基范式？

Question

将下面的语法转换为乔姆斯基范式。给出所有中间步骤。

S -> AB | aB
A -> aab|lambda
B -> bbA

好的，我做的第一件事就是添加一个新的起始变量 S0
所以现在我有

S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA

然后我删除了所有的 lambda 规则:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

然后我检查了 S->S和 A->B键入不存在的规则。这就是我想出的答案，我需要进一步做些什么还是我做错了什么？

Answer 1

维基百科说:

In computer science, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form:

• A -> BC, or
• A -> α, or
• S -> ε

where A, B, C are nonterminal symbols, α is a terminal symbol, S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol.

继续你的工作:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

而不是使用 |要表示不同的选择，请将规则拆分为多个规则。

S0 -> S
S -> AB
S -> aB
S -> B
A -> aab
B -> bbA
B -> bb

创建新规则 Y -> a和 Z -> b因为我们很快就会需要它们。

S0 -> S
S -> AB
S -> aB
S -> B
A -> aab
B -> bbA
B -> bb
Y -> a
Z -> b

S -> aB不是形式 S -> BC因为 a是一个终端。所以改 a进入 Y :

S0 -> S
S -> AB
S -> YB
S -> B
A -> aab
B -> bbA
B -> bb
Y -> a
Z -> b

对 B -> bb 执行相同操作规则:

S0 -> S
S -> AB
S -> YB
S -> B
A -> aab
B -> bbA
B -> ZZ
Y -> a
Z -> b

对于 A -> aab , 创建 C -> YY ;为 B -> bbA , 创建 D -> ZZ :

S0 -> S
S -> AB
S -> YB
S -> B
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

对于 S -> B , 复制一条规则，其中 S发生在右侧并内联规则:

S0 -> B
S0 -> S
S -> AB
S -> YB
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

处理规则 S0 -> B和 S0 -> S通过将右手边连接到其他规则的左手边。此外，删除孤立规则(其中 LHS 符号永远不会在 RHS 上使用):

S0 -> DA
S0 -> ZZ
S0 -> AB
S0 -> YB
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

我们已经完成了。呼!