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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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!