GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
878 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) recursive and not a cfl. 

asked in Theory of Computation by Active (1.8k points)  
retagged by | 878 views

3 Answers

+14 votes
Best answer

Equal No of a's ,b's and c's is not context-free, but it's complement is Context-free.

That is ,

$L$ = {$w$ |$no_a(w)\neq no_b(w)$,$w\in(a+b+c)^*$}

                           $\cup$ 

        {$w$ |$no_b(w)\neq no_c(w)$,$w\in(a+b+c)^*$}

                           $\cup$ 

       {$w$ |$no_c(w)\neq no_a(w)$,$w\in(a+b+c)^*$} 

Note: I hope it can be implemented by NPDA

answered by Veteran (53.5k points)  
selected by
This should be correct ans .Let me know if i am missing something.

@Arjun sir @Praveen sir.
yes, the other answer is for a different question..
+7 votes

Complement will include all strings which are not in the given language like $\{a,b,c,ab,ac,ba,bc,cba,aaabbc, \dots\}$

$(a^nb^nc^n)^c  = \Sigma^* - (a^nb^nc^n)$

$= \underset{\text{CFL}}{\left\{a^pb^qc^r \mid p\neq q \text{ or } q\neq r \right\}} \cup \underset{\text{Regular}}{ \left\{(a + b + c)^* ( ba + ca + cb + cba ) (a+b+c)^*\right\}}$
                   
Therefore It is a CFL as CFLs are closed under union (when we do union operation over two CFLs, we always get a CFL).

answered by Veteran (15.1k points)  

Language containing equal number of a's b's and c's....is it anbncn ..?

the question doesn't mention anything  about the order of a's b's and c's ...the above said language can be any one of the form cnanbOR bnancn OR cnbnan...

Please clarify...
 

I think NO, equal no of a's , b's and c's mean they may be in any order, $a^nb^nc^n$ is a subset of it.
Abhay wt u told is correct .but still some strings is missing for eg "aabcbcacb" this order is not satisfied by any of the above mentioned string told by u.

kunal ,  you are right... In the string with equak number os a's b's and c's , the order of a,b,c are not important.

Please refer comment from Umang Raman. that is correct to me.

Praveen sir has better answer than umang raman !
+1 vote

instead of doing all that,language is {a^nb^nc^n/n>=0}

to construct pda for this language.logic is for single 'a' push two 'a' s into the stack when it sees 'b' s and 'c' s pop it from stack.

equall number of 'a' s ,'b' s and 'c' s condition is satisfied.so this language is dcfl,complement of DCFL is also DCFL.

answered by Junior (521 points)  
a^n b^n c^n it means equal no of a's b's and c's

 what are you going to do with aabbbc   

this string is not in the language but a/c to your approach which is push 2 a's instead of 1 a .this string is going to be accepted.

how ===>push 2 a's for first a then again push 2 a's for next a then pop 3 a's with each b and in last pop last a with c it is accepted but this string is not in the language.

so your approach is failed here.

k,i have another doubt

L={a^nb^nc^n/n>=0} is CONTEXT SENSITIVE LANGUAGE.SO COMPLEMENT OF CSL IS MAY OR MAY NOT BE CSL,HOW CAN WE SAY THAT IT IS ACCEPTED BY NPDA.PLEASE CLARIFY MY DOUBT

I have same doubt the language is CSL and CSL closed under compliment then It should be CSL
its a CSL and we know by closure property that CSL are closed under complementation

so it should be CSL

but we can draw PDA for its complement by making a is not equals to b or b is not equals to c or a isnot quals to c so it is CFL too
complement of csl is csl because csl is closed under complementation and cfl also

and commplement of cfl is csl and may or may not be cfl
I think your answer is very clear the all the above... i dont know why these people making it so confusing..

Related questions

+2 votes
1 answer
2
+2 votes
1 answer
3


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,651 answers
79,695 comments
31,069 users