Question

The question asks to design CFG for the following language

{x over {a,b } x is not palindrome}

Answer 1

CFG fot all sets of strings that are not palindroem over input alphabet {a,b} is:

S->aSa | bSb | aTb | bTa

T->aT | bT | ε

These production rules will generate all set of strings that are not palindrome.

Now try to derive any string from the mentioned productions say

S->aSa

S->aaTba

S->aaεba = aaba which is not palindrome

Palindrome String : A string is said to be a palindrome if the string read from left to right is equal to the string read from right to left.

CFG for palindrome string is:

S->a | b | aSa | bSb | ε