PDA with multiple element access - $i$ - access PDA

Question

We define an $i$ - access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i>0$.

Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d > 0$, we read it as "When in state $p$, upon reading an input $x$, the stack has depth at least $d$, with $c$ at the $d$th position from the top. Transition to $q$, pop $c$, and add $c'$ at the same index as $c$.

In essence, a $1$ - access PDA is essentially a normal PDA.

How do I show that for any language accepted by an $i$ - access PDA, $\exists$ a normal PDA which accepts it as well?

I know that I have to show that in the end, any $i$ - access PDAs can be reduced down to a $1$ - access PDA. But I am not sure how to go about it.

Answer 1

Hint: replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ elements back to the stack.

Another hint: to "remember" the $d-1$ elements, construct a unique "path" for each unique combination of the $d-1$ elements. Then, you can reconstruct the stack by knowing exactly which path you took.

Note: this construction works in $3$ "phases":

• reading the first $d-1$ elements of the stack
• doing the actual transition
• returning the stack to its original way Make sure you understand how to do each of those and how they combine with each other!

Answer 2

One of the possibilities is to keep the topmost $i$ symbols of the stack in the finite memory rather than putting it on the stack.

Any simple symbol replacement of the topmost symbols can be performed in memory, rather than on the stack. If we push or pop symbols from/to the stack we also push or pop from the (shorthened) stack, shifting symbols from/to the finite memory.