この古い試験問題では、文法を 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
最初のステップでは、4 つの端末の変数を設定します。
V -> a
X -> b
Y -> c
Z -> d
2 番目のステップでは、端子を変数に置き換えます (現時点では S のプロダクションのみ):
S -> VAB|a|VA|VB|AXB|AX|XB
3 番目のステップで、VAB の AB を次のように置き換えU -> ABます。
S -> VU|a|VA|VB|AXB|AX|XB
ソリューションでは、S プロダクションの AbB と bB (AXB と XB に設定) で何が起こっているのかわかりません。これは、S プロダクションに対して提供された回答です。
S → VU|a|VA|VB|UX|b|AX|BX
AbB が UX に設定され、bB が BX に設定されているのはなぜですか? 少なくとも bB を XB に設定するべきではありませんか?