构造与下列文法等价的CNF. S→aBB|bAA B→aBa|aa|ε A→bbA|ε

# 构造与下列文法等价的CNF
# 步骤1: 将终结符转换为单个字母
S→aBB|bAA  B→aBa|aa|ε  A→bbA|ε
# 精髓：儿子的产生式全部交给爸爸。 如果A->B B->α 则去掉A->B，增加A->α

# 步骤2: 消除产生式右侧的非终结符
S→XB|YC  B→XB|aa|ε  A→ZB|ε
X→a  Y→b  Z→b

# 步骤3: 消除产生式中的长产生式
S→XB|bAA|YC  B→XB|aa|ε  A→ZB|ε
X→a  Y→b  Z→b

# 步骤4: 消除产生式左侧的非终结符
S→DE|FG  B→DE|aa|ε  A→HI|ε
X→a  Y→b  Z→b  D→X  F→Y  G→C  H→Z

# 最终得到 G1 = ( N1 , T1 , P1 , S )