How to prove that $L=\{w \mid \#a(w)=\#b(w)=\#c(w)\}$ is not context free using closure

542 Views Asked by At

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

There are 1 best solutions below

3
On BEST ANSWER

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