Context free language false proof

53 Views Asked by At

What is wrong with the following proof?

Show whether $L$ is context-free or not, where $L = \left\{ a^nb^{2n}a^n | n \geq 0\right\}$

We know $\left\{a^nb^n | n \geq 0 \right\} $ and $\left\{b^na^n | n \geq 0 \right\} $ are context-free.

Notice that, $\left\{a^nb^n \right\} $$\left\{b^na^n \right\} = \left\{ a^nb^{2n}a^n\right\}$

Since CFL's are closed under concatenation we can conclude that $L$ is also context-free.

1

There are 1 best solutions below

2
On BEST ANSWER

$ab$ is in the concatenation language but not in $L$; do you see why?

For a correct argument I suggest using the pumping lemma for context-free languages.