The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
How to prove that $\text{"complement of  L }= \{WW^R \mid W \in \{a,b\}^*\} \text{ is CFL}" $?
asked in Theory of Computation by Loyal (7.2k points)
edited by | 189 views
above is CFL. and its compl is not CFL because CFL are not closed under compl.
@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 Answer

+1 vote
Best answer
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
answered by Boss (16.6k points)
selected by
Thanks Sir.. Can you please explain 2nd possibility ie.  "Even length string which are not palindrome" with an example ??
abbb , ab ,bbab etc

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,823 questions
46,798 answers
58,885 users