I have been studying the book Introduction to Computation by Michael Sipser on my own, and I'm stuck on this exercise from the chapter on Pushdown Automato and Context-Free Languages. The exercise is to show that $$A=\{x\#y\,|\, x \neq y\}$$ is a context-free language.

I'm having a hard time proving this because of the second string not reversed. I've tried both making a context-free grammar and a pushdown automata, but in both cases I can't figure out how to make/check that the initial characters of both $x$ and $y$ are the same.

I would appreciate any hints that could help me get to the answer.

  • 3
    $\begingroup$ Because you are looking for the non-equality of the two strings you only need to find one position (in both strings) that does not contain equal characters. Can you see how to use non-determinism to do this? $\endgroup$ – Sam Jones Aug 22 '13 at 13:24
  • $\begingroup$ Oh, I see! Yes, I got it from here, thank you very much! $\endgroup$ – Milind Hegde Aug 22 '13 at 14:07