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

This language would not contain strings like catcat, zzzz, and hihi, but would contain strings like cat, mrbean, and moose.

I tried using the pumping lemma, but it seems that this language can be pumped... however, constructing a grammar for this language seems to be hard.

share|cite|improve this question
To be clear the latter "single string" comes from a regular language. – John Hoffman Oct 14 '12 at 1:34

I have a hard time believing this language is context-free. Consider a finite automaton which accepts this language. It would presumable need to store the first part on the stack, and then verify that the second part doesn't match. But how it it supposed to do that - it can only read the stack from top to bottom, not the other way round. And with the stack being the only means of unbounded memory, I don't think that reversing the stack is an option either.

This, of course, is more hand-wavering than a proof. But it might serve as motivation to continue to try to pump this until it blows up, leaving nothing but contradictions ;-)

share|cite|improve this answer
Good point. We can only look on the top of the stack... – John Hoffman Oct 14 '12 at 1:26
I'm wrong, this language is context-free as I just realized. Will update shortly! – fgp Oct 14 '12 at 1:36
Ok, that's embarrassing.. Managed to confused myself it's actually context-free for a second, and realized only after posting the comment. Oh, well... – fgp Oct 14 '12 at 1:48
Hmm, thanks, but why is it context free? A PDA can only read from the top of a stack, right? – John Hoffman Oct 14 '12 at 3:53
Note that there are languages that satisfy the (context-free) pumping lemma yet are not context-free. This looks like it's one of them. – Henning Makholm Oct 14 '12 at 11:46

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.