0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ What did you try ? what languages that are not context-free do you know ? $\endgroup$
    – Belgi
    Jan 4, 2013 at 10:15
  • $\begingroup$ 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. $\endgroup$
    – DanielY
    Jan 4, 2013 at 10:18
  • $\begingroup$ So why do you restrict yourself to showing this only with clousre properties ? $\endgroup$
    – Belgi
    Jan 4, 2013 at 10:19
  • $\begingroup$ that's the exercise's request $\endgroup$
    – DanielY
    Jan 4, 2013 at 10:26
  • $\begingroup$ @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 $\endgroup$
    – DanielY
    Jan 4, 2013 at 12:10

1 Answer 1

1
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .