Tell me more ×
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.
up vote 0 down vote favorite

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 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. – user1067083 Jan 4 at 10:18
So why do you restrict yourself to showing this only with clousre properties ? – Belgi Jan 4 at 10:19
that's the exercise's request – user1067083 Jan 4 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 – user1067083 Jan 4 at 12:10

1 Answer

up vote 1 down vote

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 :) – user1067083 Jan 5 at 16:05

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.