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

  • 2
    $\begingroup$ $x$ and $y$ can have the same size, and still $x\#y \in L$ $\endgroup$ Commented May 8, 2015 at 0:20
  • 1
    $\begingroup$ possible duplicate of Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free $\endgroup$
    – Ran G.
    Commented May 8, 2015 at 2:29
  • $\begingroup$ 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. $\endgroup$
    – kirelagin
    Commented May 8, 2015 at 6:23
  • 2
    $\begingroup$ 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. $\endgroup$
    – babou
    Commented May 8, 2015 at 11:25

3 Answers 3


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.

  • $\begingroup$ I tried to draw the automaton according to your description but I couldn't figure where the symbol $a$ should be, and I also don't quite understand how to translate "memorizes the symbol $x_i$ in its finite control" into drawing. I saw in other posts a CFG to this language and I'm aware that exists algorithm that convert CFG to PDA. Your method is different because you use nondeterminism directly, skipping the CFG. I'm working with Michael Sipser book on the topic and I couldn't found a PDA that use nondeterminism like you wrote. Will it be possible for you do draw the PDA ? $\endgroup$
    – Daniel
    Commented May 14 at 15:18

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.

  • $\begingroup$ The answer you linked to does not deal with #. $\endgroup$
    – xskxzr
    Commented May 18, 2019 at 4:57
  • $\begingroup$ @xskxzr No, but it's a trivial adaptation to add the #. $\endgroup$ Commented May 19, 2019 at 6:48
  • 2
    $\begingroup$ I don't think it's trivial... Could you please describe it in detail? $\endgroup$
    – xskxzr
    Commented May 19, 2019 at 9:08
  • 2
    $\begingroup$ @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|$. $\endgroup$
    – John L.
    Commented May 24, 2019 at 20:44
  • 1
    $\begingroup$ @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?. $\endgroup$
    – John L.
    Commented 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: DPDA

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.