The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+7 votes
1.1k 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 | 1.1k views

3 Answers

+15 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 (55.3k 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.4k 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 !
0 votes

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 (513 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



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

28,946 questions
36,792 answers
91,068 comments
34,689 users