2 Give a CFG for the following language L w w is of the fr

2) Give a CFG for the following language.

            L = {w | w is of the from 0^M1^N0^M+N}

Solution

Answer:

S -> 0A0 | B | epsilon

A -> 0A0 | B | epsilon

B -> 1B0 | epsilon

First I made minimum length strings of L - {epsilon,00,11,....so on} , so these must be generated by resulting grammar then I broke the language L,

L = 0^m 1^n 0^n 0^m

So S -> 0A0 handles for 0^m case i.e no of zero at start equals no of zero at last. And as m,n >=0 so if m=0.. then L is 1^n 0^n . So for m=0 case I put S -> B.

A ----> 0A | epsilon