0

在这个旧的考试问题中,我需要将语法转换为 CNF,但我怀疑提供的解决方案是错误的。

语法:

S -> aAB|a|aA|aB|AbB|b|Ab|bB
A -> aA|a|cC|c
B -> bB|b|dD|d
C -> cC|c
D -> dD|d

在第一步中,我为四个终端设置变量:

V -> a
X -> b
Y -> c
Z -> d

在第二步中,我用变量替换终端(现在只有 S 中的产品):

S -> VAB|a|VA|VB|AXB|AX|XB

在第三步中,我将 VAB 中的 AB 替换为U -> AB

S -> VU|a|VA|VB|AXB|AX|XB

在解决方案中,我不明白 S-productions AbB 和 bB 发生了什么(我已将其设置为 AXB 和 XB)。这是为 S-productions 提供的答案:

S → VU|a|VA|VB|UX|b|AX|BX

为什么 AbB 设置为 UX 而 bB 设置为 BX?不应该至少将 bB 设置为 XB 吗?

4

0 回答 0