# 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$ May 8, 2015 at 0:20
• possible duplicate of Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free May 8, 2015 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. May 8, 2015 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. May 8, 2015 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 #. May 18, 2019 at 4:57
• @xskxzr No, but it's a trivial adaptation to add the #. May 19, 2019 at 6:48
• I don't think it's trivial... Could you please describe it in detail? May 19, 2019 at 9:08
• @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|$. May 24, 2019 at 20:44
• @LukeMathieson Babou's answer does not imply $\{x \# y \mid |x| = |y|, x \neq y\}$ is context-free. Please also check How can $ws$ with $|w|=|s|$ and $w\not=s$ be context-free while $w\#𝑠$ is not?. May 25, 2019 at 1:06

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

                 L={x#y ∣ x, y ∈ {0,1}* ∧ x≠y}


See, To approach this, we can have followiing Cases:

Case 1: Let length of 'X' is more than length of 'Y',i.e., |x| > |y|, it should be accepted in our PDA.

Case 2: Let Length of 'X' is less than ;ength of 'Y', i.e., |X| < |Y|. it should also be accepted in our PDA.

Case 3: Let Length of 'X' is exactly equal to length of 'Y',i.e., |X| = |Y|. It SHOULD NOT BE ACCEPTED in our PDA.

 So, to solve this, Let us append an end-marker to the language at the end, which is *"\$"*. Therefore our language will be :

L$$= {x#y$$ ∣ x,y ∈ {0,1}* ∧ x≠y}


Now, Our DPDA can be look like this: i have used input alphabet (0,1) and Stack alphabet (A, B). Here "A" represents "0" and "B" represents "1".
Final States are q3 and q8.
Initial state is q0.

i hope you can find it correct!