0

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

Ilmari Karonen
  • 26,117
DanielY
  • 979
  • What did you try ? what languages that are not context-free do you know ? – Belgi Jan 04 '13 at 10:15
  • Basically it's a part of a bigger proof. I want to show that the claim "if L is context-free than mirror(L)={wwr | w is in L} is also context-free" is wrong, so I took {a^nb^n} as an example for a context free langauge and now I need to show that mirror(L), which is the lang. above, is not context free. I know that {a^nb^nc^n} is not context free. – DanielY Jan 04 '13 at 10:18
  • So why do you restrict yourself to showing this only with clousre properties ? – Belgi Jan 04 '13 at 10:19
  • that's the exercise's request – DanielY Jan 04 '13 at 10:26
  • @Belgi I'll correct myself. I can show it as I wish, except for the pumping lemma for CFL which I didn't learn yet – DanielY Jan 04 '13 at 12:10

1 Answers1

1

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^*$?

Brian M. Scott
  • 616,228