Pushing / popping the stack in reverse order in Pushdown auto-tuning

Question

So, I'm studying a test that I come up with on pushdown machines and in context-free languages, and I'm stuck on this one construct.

I have every part of this machine that works perfectly fine, with the exception of one part, which I will explain below.

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

Thus, the problem I am facing is comparing Xi with Wi, since the Wi elements are not known at the moment the machine receives the W processing, as I developed it.

If I store the contents of X when time runs out and each element is compared with the W symbol, they will exit in the reverse order and therefore consider 000111 and 111000 to be the same line, and the PDA will reject when it should clearly accept (they are different strings). This is just one example, it will also lead to incorrect analysis of other inputs.

If there is a way to move the contents of X onto the stack in the reverse order, they will slip out in their original form, which will allow me to correctly compare the contents of the strings.

If there is a way to change the contents of the stack after a normal click, it will also allow me to come to a solution.

Any help would be greatly appreciated. Thanks.

Answer 1

The solution is a bit complicated.

There really is no way to change the contents of the stack in the PDA. It is all about the non-deterministic nature of npda that makes this problem solvable.

Get started with this simpler version.

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

Decision:

Start with state q. press $ for each letter x on the kth letter (k is not important, choose k non-deterministically), then examine the kth letter and go to q0 if it is 0, or go to q1 if it was 1 Ignore the rest of x until you reach #. Put $ for each letter w until you reach the bottom of the stack (say z). Learn the kth letter w. If [you were in q0 and the letter was not 0] or [you were in q1 and the letter did not accept 1).

What is this, magic!