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.
$\begingroup$
$\endgroup$
2
-
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.SchulzCommented 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$– Hendrik JanCommented Nov 18, 2013 at 20:46
Add a comment
|