2
$\begingroup$

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.

  • 0
    To be clear the latter "single string" comes from a regular language.2012-10-14

1 Answers 1

1

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

  • 0
    Thanks, how'd you know though?2012-10-15