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.

1 Answers 1

1

$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$.
  • 1
    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 .2012-06-13