edited by
7,118 views
8 votes
8 votes
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.
edited by

3 Answers

Best answer
20 votes
20 votes

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

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

Related questions

5 votes
5 votes
2 answers
1
Pradip Nichite asked Dec 31, 2015
4,758 views
Please some one explain. why complement of this language is CFL.
3 votes
3 votes
1 answer
2
2 votes
2 votes
1 answer
4
Mahesha999 asked Dec 24, 2016
283 views
How below language is context free? I am not able to imagine what could be the behaviour of the PDA accepting this language. Can anyone give a hint?$L=\{\omega:2n_a(\omeg...