What is flaw on my proof to identify any string of $L_2$ using single stack?

44 Views Asked by At

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?

  1. Both $L_1$ and $L_2$ are context-free.
  2. $L_1$ is context-free while $L_2$ is not context-free.
  3. $L_2$ is context-free while $L_1$ is not context-free.
  4. 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?

1

There are 1 best solutions below

3
On BEST ANSWER

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