在这个旧的考试问题中,我需要将语法转换为 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 吗?