1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by frafl, Luke Mathieson, D.W., Raphael Nov 18 '13 at 21:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 '13 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$ – Hendrik Jan Nov 18 '13 at 20:46