Consider the following languages:
$L_1=\{a^nb^mc^{n+m}:m,n≥1\}$
$L_2=\{a^nb^nc^{2n}:n≥1\}$
Which one of the following is TRUE?
- Both $L_1$ and $L_2$ are context-free.
- $L_1$ is context-free while $L_2$ is not context-free.
- $L_2$ is context-free while $L_1$ is not context-free.
- Neither $L_1$ nor $L_2$ is context-free.
My attempt:
$L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ is context free language, as uses single stack : push all a's on an empty stack and also push all b's on stack, then pop single b form stack then a's, if b's were empty. When input is empty then and stack is empty then string is from $L_1$ else not.
Well, $L_2=\{a^nb^nc^{2n}:n≥1\}$ I know that $L_2$ is not context free but context sensitive language. Still, I'm arguing that we can follow the procedure for $L_2$ as I've describe above for any string of $L_1$.
Can you explain, please? What is flaw on my proof to identify any string of $L_2$ using single stack?
For $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ number of $a's$ and $b's$ independent while for $L_2=\{a^nb^nc^{2n}:n≥1\}$ number of $a's$ and $b's$ dependent. So we can't use single stack to identify any string of $L_2$.