Convert each of the following context free grammars into Cho

Convert each of the following context free grammars into Chomsky Normal Form:

G1 : S ABb | a

A aaA | B

B bAb | c

G2 : S aSb | bSa | a | b

Solution

G1:

Add followring rules:

X ->a

Y->b

S-> ABX | a

A -> XXA | B

B -> YAY | C

Now

Add following rules:

M -> BX

N - > XX

O->YA

Now our final grammar becomes:

S-> AM | a

A -> NA | c

B -> OY |c

M -> BX

N -> XX

O -> YA

X -> a

Y ->b

G2: Add following rules:

X -> a   and Y -> b

Now grammar becomes:

S -> XSY | YSX |a|b

add,   M -> XS and N-> YS

Now grammar becomes, S -> MY |NX|a|b