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.

retagged | 878 views

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

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

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

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

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.

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