Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
What did you try ? what languages that are not context-free do you know ? – Belgi Jan 4 '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 4 '13 at 10:18
So why do you restrict yourself to showing this only with clousre properties ? – Belgi Jan 4 '13 at 10:19
that's the exercise's request – DanielY Jan 4 '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 4 '13 at 12:10

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

share|cite|improve this answer
Thanks alot Brian :) – DanielY Jan 5 '13 at 16:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.