This question already has an answer here:

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


marked as duplicate by jmite, David Richerby, vonbrand, Raphael Mar 8 '16 at 14:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I think OP only mentions $L_1$ as a language known to be context-free, and feels that therefore, so should be $L_2$ (being the sublanguage for $m=n$). $\endgroup$ – Klaus Draeger Mar 6 '16 at 9:54
  • $\begingroup$ @KlausDraeger that is what I mean. Nobody understands what I ask. I ask the differnce, I know how one language is CFL but not how L2 is not. $\endgroup$ – Rahul Bali Mar 6 '16 at 11:11
  • $\begingroup$ By representation, I mean, what machine can work such language practically? $\endgroup$ – Rahul Bali Mar 6 '16 at 13:29
  • $\begingroup$ Turing machines can accept such languages in a jiffy. $\endgroup$ – Shreesh Mar 6 '16 at 13:30
  • $\begingroup$ And even linear bounded automata. $\endgroup$ – Shreesh Mar 6 '16 at 13:30

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.

  • $\begingroup$ There is a thing, the grammar written is not applicable for L2. $\endgroup$ – Rahul Bali Mar 8 '16 at 10:12
  • 2
    $\begingroup$ In my opinion that's the most important part of this answer, because that's exactly the intuition you should have: "$L_2$ [...] 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." $\endgroup$ – maybeshewill Mar 8 '16 at 11:26

Here is a simpler example: $$ \begin{align*} L_1 &= \{ a^n b^m : n,m \geq 0\} & \text{is regular}, \\ L_2 &= \{ a^n b^n : n \geq 0\} & \text{isn't regular}. \end{align*} $$

More generally, if a language $L$ is regular (or context-free), we are not guaranteed that any sublanguage is regular (or context-free). Indeed, any language over an alphabet $\Sigma$ is a subset of the regular language $\Sigma^*$, but not all of them are regular (or even context-free).

You can say, however, that if $L$ is regular (or context-free) and $M$ is a regular language, then $L \cap M$ is regular (or context-free). For example, $L_3 = \{ w : \#_a(w) = \#_b(w) \}$ is context-free and $a^*b^*$ is regular, and so $L_3 \cap a^*b^* = \{a^nb^n : n \geq 0\}$ is context-free.

  • $\begingroup$ This is context of regular and CF languages. Instead, CF and CS language would explain it better. $\endgroup$ – Rahul Bali Mar 8 '16 at 10:04

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