[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