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 (8.4k points)
edited by | 278 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 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
answered by Boss (17.4k points)
edited ago by
Thanks Sir.. Can you please explain 2nd possibility ie.  "Even length string which are not palindrome" with an example ??
abbb , ab ,bbab etc



@Mk Utkarsh

brother according to the answer, on NPDA, while "abba" --- W = ab

you go push a, then on getting b ===> it is not matched with top of stack ===> accept

but it shouldn't accept, right ?


@Shaik Sir, Here we have to guess the halfway point non-deterministically. After guessing halfway point, If next character of the input string does not match with the top of the stack then we go to final state and accept it and if matches then we don't go to dead state ..we keep doing it until we find atleast one mismatch and if no mismatch then we go to dead state.

here for abba , here halfway point is after "ab" next input character is 'b' , so here no mismatch has been occurred. So, we pop one time.. now,again check ..again no mismatch because 'a' on stack now matches with 'a' of input string. So now, go to dead state and reject it because we didn't find atleast one mismatch.

You can get the idea from this video lecture. Kindly watch it from @47:32.


brother, if i guess halfway point, then it is easy...

but i am not getting, how remaining possibilities are rejected ?

i mean 100 001 is should be rejected, on non-deterministic you will think after reading 1, it came 0 ===> it is accepted due to i think it is 2-length string only ===> How will take care of this ?


if it is W.W$^R$, then automatically those are rejected, that is not a problem, but when it's complement how we will take care of those things ?
@Shaik Sir,  for 100 001,  non-deterministic machine guesses the halfway point which is after 100 then here top of the stack is 0.. Now it will check that it  matches with 1st character of remaining input string 001 or not.. Here 1st symbol of remaining input is 0 ...  Now match top of the stack which is 0 with 1st character of remaining input which is 0..since it matches. So repeat it again this procedure until we get one mismatch..So here after popping 0 with top of stack 0 and 1st character of remaining input is 0..again match.. So pop it.. Now top of stack 1 and 1st character of remaining input is 1..again match and pop it.. Now all symbols are popped off and we did not find any mismatch.. So we go to dead state...

It is same like ww^r.. After reaching halfway point,  we check for matches but here we check for atleast one mismatch ...

@ankitgupta.1729 explanation is perfectly correct for 100 001 since at end we don't have any mismatch and no input string means its an even length palindrome so go to non final state 

brother, what i am saying is, " From the half point you will get it as reject",

But before reaching the half point how you are going to reject them ?

Note that, the string which is not in the language should reject in all the ways by NPDA
I don't have any mechanism right now which can reject string before reaching half way point or at half way itself, in above method string which are not part of language are rejected perfectly.

i hope you understood what i am asking,

if there is atleast one way to accept, then it is accepted ===> string in the language ( we use this in WW$^R$ language)

but it doesn't mean if there is atleast one way to reject, then it is reject ===> string not in the language

there should be some mechanism with PDA, otherwise it can't be CFL.... but i am not getting that mechanism, if you get it, please share it here :)


@Shaik Masthan no I am not getting your doubt at all, answer given and video explains it.  If you have doubt regarding how we will select mid point then see video from start.


ok, no problem.... i cleared my doubt from the video !

thanks for sharing the video @ankitgupta.1729

and responding on my reply's @Tesla! @ankitgupta.1729



One thing tell me, $ww^{r}$ NCFL

and NCFL cannot closed under complement

then how complement of $ww^{r}$ is CFL?

Another point is

Can u tell me what are the string belong to in reverse of $ww^{r}$?


NCFL cannot closed under complement

i hope you mistakenly write it is as NCFL, actually it is NPDA ===> CFL but not DCFL

CFL are not closed under complementation, yes it is true.

But it doesn't mean, complement of CFL can't be CFL.

it means, CFL complement may or may not be CFL.

in this CFL = { WW$^R$ }, it's complement also a CFL but it is not DCFL

   ===> NPDA exist for complement of { WW$^R$}


Can u tell me what are the string belong to in reverse of ww$^r$?

Strings belongs to  WW$^R$ = {00,11,0110,1001,0000,1111,......}

Strings belongs to  $(WW^R)^R$ = Strings belongs to  WW$^R$ = {00,11,0110,1001,0000,1111,......}

Strings belongs to  $(WW^R)^C$ = ∑* - Strings belongs to  WW$^R$ = {0,1,01,10,000,001,......}

Related questions

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

44,337 questions
49,834 answers
65,874 users