edited by
5,066 views
2 votes
2 votes
How to prove that $\text{"complement of  L }= \{WW^R \mid W \in \{a,b\}^*\} \text{ is CFL}" $?
edited by

1 Answer

Best answer
4 votes
4 votes
WW$^{R}$ means even length palindrome so its complement must accept

1) Odd length string

2) Even length string which are not palindrome

So here we can get help of non determinism we perform push and at arbitrary point X assuming it to be half of string now we pop so there are few possibility

1) at least one symbol did not match (success)

2) Stack is empty and no input string is remaining to read (failure)

case 1 is definitely true for odd length string thus accepting but it also help in accepting even length string which are not palindrome.

case 2 is true when string is even length palindrome so thus at the end we will make an transaction to non final state
edited by

Related questions

0 votes
0 votes
0 answers
1
Manu Thakur asked Sep 29, 2017
574 views
Is the following language CFL?L = complement of {$a^ib^jc^k$ | i!=j and j!=k}
5 votes
5 votes
2 answers
2
Pradip Nichite asked Dec 31, 2015
4,758 views
Please some one explain. why complement of this language is CFL.
8 votes
8 votes
3 answers
3
Payal Rastogi asked Nov 2, 2015
7,120 views
The complement of the language $L$ containing an equal number of $a's$,$b's$ and $c's$ is (a) regular(b) context free(c) context sensitive but not context free(d) recursi...