# Find a pushdown automaton for { x#y ∣ x ≠ y }

I was told to built a PDA that recognizes the following language:

$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$

My attempt is basically to push $x$ to the stack for every $1$ and $0$ read. And then pop them for the second half. If it finishes and the stack is still not empty, it will be accepted. Or if it hasn't finished reading but the stack is empty already it will also accept.

Am I approaching this correctly? I can easily do the CFG but I'm told that it's easier to do the PDA from scratch rather than converting it since it needs to be in CNF.

Any help appreciated

• $x$ and $y$ can have the same size, and still $x\#y \in L$ – André Souza Lemos May 8 '15 at 0:20
• possible duplicate of Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free – Ran G. May 8 '15 at 2:29
• Hm, I agree that it’s not very difficult to come up with a grammar for this language. And once you’ve got the grammar it’s pretty straightforward to turn in into a non-deterministic PDA based on the same idea. – kirelagin May 8 '15 at 6:23
• This is not a duplicate of Show that {xy∣|x|=|y|,x≠y} is context-free. The marker # separating x and y makes the problem simpler. Furthermore, the referenced problem assumes |x|=|y|, which is not the case here. It is true that the answer to the older question could be used, but it is not the simplest way to build the PDA. – babou May 8 '15 at 11:25

Since you have a marker $\#$ separating $x$ and $y$, the solution is rather easy. The PDA must first decide non-deterministically whether it will attempt to check that $|x|\neq|y|$ or whether $x$ and $y$ differ for their $i$-th symbol, i.e. whether $x_i\neq y_i$. This corresponds to two distinct sets of states.

The first case can be dealt with as you suggest.

In the second case, the automaton scans the input, and stores a symbol $a$ in its stack to keep count. At the $i$-th symbol, chosen non-deterministically, it decides to check whether that is the symbol rank for which $x_i\neq y_i$. So it memorizes the synbol $x_i$ in its finite control (meaning that the states now used have a component indicating whether a $0$ or a $1$ was found). Then, the PDA scans the input without memorizing anything until it scans the symbol $\#$. Then it start scanning the $y$ part, popping the stack for each symbol read. When the stack is empty, it is reading the symbol $y_i$, and it can check whether it is different from $x_i$ memorized in the finite control. If it is different, the PDA can accept the string, and does not even need to scan the rest.

If the end of the string is reached before the stack is empty, the automaton can accept too, though this can also be handled by the first case.

Your approach will work when $|x| \neq |y|$, but not for something like $1\#0$, which should also be in the language.

For the case where $|x| = |y|$, we happen to already have an answer, which can be easily adapted to suit (there's a PDA there, but you can also convert the CFG to a PDA, or just take inspiration from the answers).

The only part left is deciding which case you're in. As the PDA can't read ahead and count, you have two options, try and both count and guess the incorrect character at once, or use nondeterminism to guess at the beginning which case the input falls into. Neither are particularly harder than the other, so it's more a matter of how comfortable you are with the idea of each.

• The answer you linked to does not deal with #. – xskxzr May 18 '19 at 4:57
• @xskxzr No, but it's a trivial adaptation to add the #. – Luke Mathieson May 19 '19 at 6:48
• I don't think it's trivial... Could you please describe it in detail? – xskxzr May 19 '19 at 9:08
• @xskxzr Just see Babou's answer, he has already detailed it, so it doesn't seem worthwhile to type it out again in a hard to read comment. – Luke Mathieson May 19 '19 at 9:42
• @xskxzr You are right that this answer is misleading. That answer can NOT be adapted to case here since the language $\{x\#y\mid |x|=|y|, x\not=y\}$ is not context-free. It is, in fact, much more natural to consider that there is only one case, "the only part left", which should subsume the the case where $|x|=|y|$. – John L. May 24 '19 at 20:44