1
$\begingroup$

How can I prove that the language $L = \{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure?

EDIT :

I know that the language $L_1 = \{a^i b^i c^i \mid i\geq 0\}$ is not a context free language. Now I'm trying to find another language $L_2$, where $L_2$ would be a regular language, in order to make a contradiction, since if $L_1$ is context free and $L_2$ is a regular language, then $L_1 \cap L_2$ is also context free.

$\endgroup$
1
$\begingroup$

$L_1$ is included in $L$: can you find a regular language $R$ so that $L_1=L\cap R$?

Hints:

  • $R$ needs to reject symbols other than $a,b,c$.
  • $R$ needs to enforce the order between appearances of $a$, $b$ and $c$.
$\endgroup$
  • 1
    $\begingroup$ How about L = {a*b*c*} ? $\endgroup$ – JAN Jun 13 '12 at 2:36
  • $\begingroup$ Exactly! (but I called it $R$ since you already defined $L$ to be the language of the original question) Now can you finish the proof? What would happen if $L$ was context-free? $\endgroup$ – Generic Human Jun 13 '12 at 2:39
  • 1
    $\begingroup$ From here it's pretty simple , since L3={a*b*c*} is a regular language and L={w|#a(w)=#b(w)=#c(w)} is a context free language , then L1∩L3` would be also context free . But we know that L4 = {a^i b^i c^i | i>=0} = L1∩L3` is not context free , hence we have a contradiction . $\endgroup$ – JAN Jun 13 '12 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.