The Gateway to Computer Science Excellence
+7 votes
2.2k 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. 

in Theory of Computation by Junior (933 points)
retagged by | 2.2k views
0
what about the complement of a^nb^na^n?

3 Answers

+16 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

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

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

L=anbncn

L is CSL language so it is closed under complement. 

How does its complement CFL ?

 

 

 

 

 

 

 

0
CFL is definitely CSL
0
Got it
+8 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).

by Boss (16.3k points)
0

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...
 

+2
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.
0
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.
0

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.

0
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.

by (367 points)
0
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.
0

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

0
I have same doubt the language is CSL and CSL closed under compliment then It should be CSL
0
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
0
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
0
I think your answer is very clear the all the above... i dont know why these people making it so confusing..
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
50,650 questions
56,193 answers
193,988 comments
94,863 users