I'm trying to create a PDA for $\{xy \mid |x|=|y| \text{ and } x \ne y\}$ over the alphabet $\Sigma = \{a, b\}$. But I don't know how the PDA will know if the two strings $x$ and $y$ are not equal. Please help me create this PDA step by step.

  • 1
    $\begingroup$ Use nondeterminism. Try to guess the position $i$ where $x$ and $y$ differ. You have to verify your guess. Use the stack to count to position $i$. $\endgroup$
    – A.Schulz
    Nov 18, 2013 at 15:13
  • $\begingroup$ This language is context-free! and A.Schultz has a good hint. Do not try to find the middle of the word, just guess position $i$. (I stress this as people are presently trying to prove the contrary in the answers.) The question is more or less a duplicate of 16753 and 307 $\endgroup$ Nov 18, 2013 at 20:46


Browse other questions tagged or ask your own question.