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 take $C_2$ =>b

Consider B =>bB

Substituting $C_2$ =>b, we get

B =>$C_2B$ which is a CNF

Consider S =>aAbB

Substituting values for $C_1 and C_2$, we get

S =>$C_1AC_2B$

Let $C_3$ =>$C_1A$

Substituting this value, we get

S =>$C_3C_2B$

Let $C_4$ => $C_3C_2$

Substituting this value, we get

S =>$C_4B$ which is a CNF