Pushing/popping stack in reverse order in a Pushdown Automaton

Question

So I'm studying for a test I have coming up on pushdown automata and context-free languages and I'm stuck on this one construction.

I have every part of this automaton completely working perfectly except for one part which I will explain below.

The language it needs to recognize is : { x#y#z#w | x, y, z, w in {0, 1}+ with x ≠ w and y ≠ z }.

So the issue I'm having is comparing Xi to Wi, since the elements of Wi are not known at the time the automaton gets to processing W, the way that I have it designed.

If I store the contents of X, when time comes to pop off and compare each element to those of W, they will pop off in reverse order and therefore consider 000111 and 111000 to be the same string and the PDA will reject, when it should clearly accept (they are different strings). This is just one example, this will also cause other inputs to be incorrectly analyzed.

If there is a way to push the contents of X onto the stack in reverse order, they will pop off in their original form, allowing me to correctly compare the contents of the strings.

If there is a way to reverse the contents of the stack after pushing normally, this will also allow me to arrive at the solution.

Any help would be greatly appreciated. Thanks.

Answer 1

The solution is a bit tricky.

There is actually no way to reverse the contents of stack in PDA. It's all about the non-determinism nature of npda which makes this problem solvable.

Start with this simpler version

L = {x#w: x,w in {0,1}+ and x≠w}.

Solution:

Start with state q. push a $ for every letter of x til the k'th letter (k is not important, choose k non-deterministically), then examine the k'th letter and go to q0 if it was 0 or go to q1 if it was 1. Ignore the rest of x till you reach #. Pop a $ for each letter of w until you reach the bottom of stack(say z). Examine the k'th letter of w. If [you were at q0 and the letter wasn't 0] or [you were at q1 and the letter wasn't 1] accept.

That's it, wizardry!