Question

Convert the grammar G = ({S,A,B,C},{a,b},P,S), where P is given below, into the Chomsky Normal Form.

S −→ AaA | AB

A −→ BB | bAA | ε

B −→ bS | b | ε

Answer 1

S → AaA | AB
A → BB | bAA | ε
B → bS | b | ε

Remove epsilon transitions

S → AaA | AB | A
A → BB | bAA | ε | B
B → bS | b

S → AaA | AB | A | aA | Aa | a | epsilon
A → BB | bAA | B | bA | b
B → bS | b

Remove UNIT rules

S → AaA | AB | aA | Aa | a | epsilon | BB | bAA | bS | bA | b
A → BB | bAA | bS | bA | b
B → bS | b

Remove mixed rules

S → AMA | AB | MA | AM | a | epsilon | BB | NAA | NS | NA | b
A → BB | NAA | NS | NA | b
B → NS | b
M -> a
N -> b

Change to final CNF

S → CA | AB | MA | AM | a | epsilon | BB | ND | NA | b | NS
A → BB | ND | NA | b | NS
B → NS | b
M -> a
N -> b
C -> AM
D -> AA

Please up vote. I need it very badly right now.