Write a CFG which generates string of palindrome of binary number

Write a CFG which generates string of palindrome of binary number.

Ans.  

        For constructing a grammar G of all pallindroms, we use the recursive definition as-

            (i)  ^ is a pallindrome.

            (ii)  0,1 are pallindroms.

            (iii)  If x is a pallindrome, then 0x0 and 1x1 are also pallindroms.

    ∵ The CFG, G ({S}, {0,1},P,S)

    Where, P the production set, consists of =>

        P : {S → AB| ^ ,

            A → 0A|1A|0|1 ,

            B → 0 B|1B|0|1 }

    To prove that we are correct, taking an example of a pallindrome, say, 0011100.

So, it can be derived as =>

                    S → AB

                       => 0AB [∵ A → OA]

                       => 00B [∵ A → O]

                       => 001B [∵ B → 1B]

                       => 0011B [∵ B → 1B]

                       => 00111B [∵ B → 1B]

                       => 001110B [∵ B → 0B]

                       => 0011100 [∵ B → 0]

    Therefore, it is the required CFG.