114 views
How to prove that $\text{"complement of L }= \{WW^R \mid W \in \{a,b\}^*\} \text{ is CFL}"$?
edited | 114 views
0
above is CFL. and its compl is not CFL because CFL are not closed under compl.
0
@Shubhanshu Sir,  Cfls are not closed under complement operation.. It means  after complement,  we may or may not get CFL.. But here we surely get cfl after complement but I don't know how bcoz here complement contains ww type strings also which gives csl but not cfl type language... Please correct me sir..

+1 vote
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 not 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
selected
0
Thanks Sir.. Can you please explain 2nd possibility ie.  "Even length string which are not palindrome" with an example ??
0
abbb , ab ,bbab etc
0
Thanks!