Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
    
Thanks alot Brian :) –  DanielY Jan 5 '13 at 16:05
add comment

Your Answer

 
discard

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.