1

I am attempting to construct a PDA of a language that looks like $\ {x\#y\#z}\ $

$x,y,z $ $\epsilon$ $\{ 0,1\}^{+}$

The PDA is nondeterministic, there are some other requirements, but primarily there is one I don't even know how to approach.

There exists odd value $i \ with \ x_i ≠ y_i \ or \ x_i ≠ z_i \ or \ y_i ≠ z_i$

Initially, my instinct was (for the $ x_i ≠ y_i $ part at least) was to record all values of the string from the X part (either 0 or 1) on the stack and then check each of those against the Y values. But the stack pushes the X part of the string in reverse order and there's no way to start reading from the end of the Y section of the string. So how do I attempt this?

wontonman2
  • 13

1 Answers1

0

I suppose that with $x_i$ you denote the $i$-th symbol of the string x.

You have to use the non-determinism here. For every odd position i and pair x/y, x/z, and y/z you need to have a computation that guesses that i is the position that verfies the condition in the pair you guess.

For example, first decide that x/y is the pair you look at. Then put some counting symbol on the stack. At any odd position you can chose that this is "your" position. Then you remember the symbol read in this position in the PDA's state. Run to the beginning of y. Pop counter symbols as you advance. When the counter is empty, compare the current symbol to the one remembered in the state. If they match, accept.

So if the string fulfills your condition, there will be a computation that accepts it (and many others that do not, but that is non-determinism).

Peter Leupold
  • 1,220