-1
1
$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?
Rahul Bali
Posted 2016-03-06T06:42:14.787
Reputation: 141
5
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.
Shreesh
Posted 2016-03-06T06:42:14.787
Reputation: 4 617
There is a thing, the grammar written is not applicable for L2. – Rahul Bali – 2016-03-08T10:12:14.343
2In 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." – maybeshewill – 2016-03-08T11:26:13.330
2
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.
Yuval Filmus
Posted 2016-03-06T06:42:14.787
Reputation: 245 786
This is context of regular and CF languages. Instead, CF and CS language would explain it better. – Rahul Bali – 2016-03-08T10:04:40.237
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$). – Klaus Draeger – 2016-03-06T09:54:45.650
@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. – Rahul Bali – 2016-03-06T11:11:14.373
By representation, I mean, what machine can work such language practically? – Rahul Bali – 2016-03-06T13:29:44.063
Turing machines can accept such languages in a jiffy. – Shreesh – 2016-03-06T13:30:25.630
And even linear bounded automata. – Shreesh – 2016-03-06T13:30:51.413
Hmm... Linear bounded automata, that's not what I know. How does that work? Can you direct me where I could learn that? – Rahul Bali – 2016-03-06T13:33:32.880
Let us continue this discussion in chat.
– Rahul Bali – 2016-03-06T13:35:48.173Hint: closure of CFL against (inverse) homomorphism can be used to show both claims. – Raphael – 2016-03-08T14:14:54.930