[Solved]: How is $a^nb^nc^{2n}$ not a context free language, where as $a^nb^mc^{n+m}$ is?

Problem Detail: 

$L_1 = \{a^mb^nc^{m+n}: n,m>1\}$

I know $L_1$ is CFL and works with a pushdown automata.

$L_2 = \{a^nb^nc^{2n}: n>1\}$

The language $L_2$ should also be a CFL because it looks similar, but in my book $L_2$ is not a context-free language. I just can't figure out how.

Why is the language $L_2$ not context-free and what is it then? How can it be represented?

Asked By : Rahul Parashar

Answered By : Shreesh

Have a look at the proof at the link: Is $a^n b^n c^n$ context-free?. Though the language $L_2$ is little bit different, the proof is (almost) same. There is a proof of this language in wikipedia too.

$L_1$ is a context-free language.

$L_2$ language is a context-sensitive-language. It is also in P, Recursive, RE, PSPACE, NP, and all the superclasses of CSL. Every language belongs to the class of all languages $\mathscr{P}({\Sigma^*})$.

The context sensitive grammar for the language $L_2$ similar to as given in the wiki is as following:

$S \rightarrow a b C$
$S \rightarrow a S B C$
$C B \rightarrow W B$
$W B \rightarrow W X$
$W X \rightarrow B X$
$B X \rightarrow B C$
$b B \rightarrow b b$
$C \rightarrow cc$

$L_2$ has also tree-adjoining grammar whose language class is a proper subset of context sensitive languages. Since $L_2$ has a context-sensitive grammar, it is accepted by some linear bounded automata.

As to why $L_2$ is not context-free where as $L_1$ is context free, CFL's are not closed under subset operation. Consider the following:

$\{a^p\ |\ p $ is prime $\}$ is not a CFL, where as $\{a^n\ |\ n > 1\}$ is a CFL. This is because there is an additional condition on $n$ and the pushdown automata cannot check this additional condition.

Here, $L_2$ can be written as shown here:

$L_2 = \{a^nb^mc^{n+m}\ | \ n,m >1$ and $n=m \}$ is not a CFL where as $L_1$ is, because of additional condition $n=m$ and a pushdown automata will not be able to check this additional condition.

The language $L_2$ is accepted by Linear Bounded Automaton or Two-Stack PDA.

The question, "which class a language belongs?" is meaningless, because you can construct any number of language classes to which a particular language belongs. Heck, it will belong to its own language class too. The question "which class among the known hierarchy of language classes a language belongs?" might be more meaningful. But probably you meant this only when you asked the question.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54069