Show with closures that L is not context-free

237 Views Asked by At

Consider this language:

$$ L = \{a^n b^{2n} a^n \mid n \ge 0\}$$

I need to show only with closures that it's not context-free. (Actually, I can show it as I wish, except for the pumping lemma for context-free languages, which we haven't studied yet.)

1

There are 1 best solutions below

0
On

HINT: Consider the homomorphism $\varphi(a)=\varphi(c)=a,\varphi(b)=bb$; what language is

$$\{\varphi^{-1}(w):w\in L\}\cap L_0\;,$$

where $L_0$ is the language generated by the regular expression $a^*b^*c^*$?