Convert the following CFG to CNF

S =>aAbB

A =>aA|a

B =>bB|b

If we replace A =>a, we would get A =>AA, which would cause a left recursion Hence, we need another production rule to hold the terminal value of „a‟

Let $C_1$ => a

Consider A =>aA

Substituting $C_1$ =>a, we get

A =>$C_1A$ which is a CNF

Similarly, let us …