Convert the grammar S rightarrow aSbSabab into Chomsky norma

Convert the grammar S rightarrow aSb|Sab|ab into Chomsky normal form. Transform the grammar

Solution

Answer:

S ---> aSb| Sab|ab

Make start symbol S in non-recurrsive

S----> S\'

S\'---> aS\'b|S\'ab|ab

Now do the following

S--->S\'

S\'---> AS\'b|S\'Ab|Ab ( we replaced \"a\" with \"A\" )

Now replace \"b\" with \"B\" , therefore final CNF form will be :

S--->S\'

S\'--> AS\'B|S\'AB|AB

A---> a

B---> b