PDA-er Pushdown Automaton Proof

Before proving that we can convert between PDAs and PDA-er code, we prove that we can use a different definition of a PDA. Specifically, we prove that we can use a transition function \delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q\times\Gamma\cup\{\epsilon\}\} instead of a transition function \delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q\times\Gamma^*\}. That is, we want to show that a PDA that can only push one symbol to the stack per transition has the same computing power as a regular PDA, which can push a whole word to the stack per transition. We call a PDA that can only push one symbol to the stack per transition a single-push PDA or SPPDA.
One direction is obvious: every SPPDA is by definition a regular PDA, since it uses a subset of \Gamma^*: the words of length 0 or 1. The other direction requires more work.
Formally, given any PDA M=(Q,\Sigma,\Gamma,\delta,q_0,Z,F) where Q is the set of states, \Sigma is the set of input symbols, \Gamma is the set of stack symbols, \delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q\times\Gamma^*\} is the transition function, q_0\in Q is the initial state, Z\in\Gamma is the initial stack symbol, and F\subseteq Q is the set of accepting states, we may form a SPPDA M'=(Q',\Sigma,\Gamma,\delta',q_0,Z,F), where Q'\supseteq Q and \delta':Q'\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q'\times\Gamma\cup\{\epsilon\}\}, that behaves identically to M.
The process is as follows:
 For every transition M has of the form (q_j,w)\in\delta(q_i,\sigma,\gamma), where w=\gamma_1\gamma_2\dots\gamma_n and n\geq2:
 
 Create n-1 new states \{q_1,q_2,\dots,q_{n-2},q_{n-1}\}\in Q'-F
 Let \delta'(q_i,\sigma,\gamma)=\{(q_1,\gamma_1)\}
 For k\in\{2,\dots,n-1\}, let \delta'(q_{k-1},\epsilon,\epsilon)=\{(q_k,\gamma_i)\}
 Let \delta'(q_{n-1},\epsilon,\epsilon)=\{(q_j,\gamma_n)\}
 
 
 For all other transitions of M, let \delta'(q_i,\sigma,\gamma)=\delta(q_i,\sigma,\gamma)
This means that if we run M' from state q_i on the input \sigma with \gamma on the top of the stack, after 1 step, M' will be in state q_1 and will have pushed \gamma_1 to the stack. After another step, it will be in state q_2 and will have pushed \gamma_2 to the stack. This process will continue until it is in state q_{n-1}, and after one more step it will be in state q_j and will have pushed \gamma_n to the stack. Therefore, after n steps, M' will have moved from state q_i to state q_j and will have pushed \gamma_1\gamma_2\dots\gamma_n=w to the stack, meaning it has the exact same behavior as M.
Therefore, since a SPPDA is a PDA, and since we can convert any PDA into an equivalent SPPDA, a SPPDA and PDA have the same computing power.
----
Now we show that we can convert any SPPDA into PDA-er code. Suppose we are given a SPPDA M=(Q,\Sigma,\Gamma,\delta,q_0,Z,F), where Q is the set of states, \Sigma is the set of input symbols, \Gamma is the set of stack symbols, \delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q\times\Gamma\cup\{\epsilon\}\} is the transition function, q_0\in Q is the initial state, Z\in\Gamma is the initial stack symbol, and F\subseteq Q is the set of accepting states.
Let [x] denote the binary representation of x\in Q\cup\Sigma\cup\Gamma\cup\{\epsilon\} (note that [\epsilon] is equivalent to an empty character). To convert M to PDA-er code, we use the following algorithm:
 For some q_{-1}\notin Q, write .[q_{-1}].
 Write ---[Z]-[q_0]-
 If q_0\in F write ..[q_0]., otherwise write .[q_0].
 For each (\sigma,\gamma_i)\in(\Sigma\cup\{\epsilon\})\times\Gamma:
 
 For each (q_j,\gamma_j)\in\delta(q_0,\sigma,\gamma_i), write -[\sigma]-[\gamma_i]-[\gamma_j]-[q_j]-
 
 
 For each state q_i\in Q-\{q_0\}:
 
 If q_i\in F write ..[q_i]., otherwise write .[q_i].
 For each (\sigma,\gamma_j)\in(\Sigma\cup\{\epsilon\})\times\Gamma:
 
 For each (q_k,\gamma_k)\in\delta(q_i,\sigma,\gamma_j), write -[\sigma]-[\gamma_j]-[\gamma_k]-[q_k]-
 
 
 
 
 Write !
The code created by this process will have q_{-1} as a starting state, since it is the first state specified. However, the only valid transition from q_{-1} is \delta(q_{-1},\epsilon,\epsilon)\ni(q_0,Z). This means that after 1 step, the PDA defined by this code will be in state q_0 and have Z on the stack; in other words, it will be in the same position M is at step 0. For every q\in F, it will be accepting, since it will be written as ..[q]., and for every p\in Q-F, it will be failing, since it will be written as .[p].. Because M is a PDA, we know that \delta(q,\sigma,\gamma) is not defined for all (q,\sigma,\gamma)\in Q\times(\Sigma\cup\{\epsilon\})\times\Gamma. We therefore know that every transition of M will be encoded, since we iterate through all (q,\sigma,\gamma)\in Q\times(\Sigma\cup\{\epsilon\})\times\Gamma, encoding the proper transition if it exists, and otherwise not encoding it. Therefore, the code correctly encodes M.
Assuming that we can look up \delta(q,\sigma,\gamma) in O(1) time, this algorithm runs in time O(|Q|\cdot|\Sigma|\cdot|\Gamma|), since we iterate through each q\in Q, and for each state, we iterate through each (\sigma,\gamma)\in(\Sigma\cup\{\epsilon\})\times\Gamma. It uses no additional storage.
The PDA-er code produced by this algorithm will encode each state once and each transition once. This means that if M is a minimal SPPDA—that is, it has no unnecessary states or transitions—this is the shortest code that completely encodes M.
----
Next, we show that we can convert any valid PDA-er code into a SPPDA.
To do this, we use the following algorithm (see PDA-er's Python interpreter for a code example):
 Create a PDA M=(Q=\{\},\Sigma=\{\},\Gamma=\{\},\delta=\{\},q_0=\mathrm{NULL},Z=\epsilon,F=\{\})
 Let c=0
 While there is still code to read (i.e., we have not yet encountered a !):
 
 If we encounter code of the form ..[q].:
 
 If q_0=\mathrm{NULL}, let q_0=q
 If q\notin Q, let Q=Q\cup\{q\}
 If q\notin F, let F=F\cup\{q\}
 Let c=q
 
 
 If we encounter code of the form .[q].:
 
 If q_0=\mathrm{NULL}, let q_0=q
 If q\notin Q, let Q=Q\cup\{q\}
 If q\in F, let F=F-\{q\}
 Let c=q
 
 
 If we encounter code of the form -[\sigma]-[\gamma_i]-[\gamma_j]-[q]-:
 
 If \sigma\notin\Sigma, let \Sigma=\Sigma\cup\{\sigma\}
 If \gamma_i\notin\Gamma, let \Gamma=\Gamma\cup\{\gamma_i\}
 If \gamma_j\notin\Gamma, let \Gamma=\Gamma\cup\{\gamma_j\}
 If c\notin Q, let Q=Q\cup\{c\}
 If q\notin Q, let Q=Q\cup\{q\}
 Let \delta(c,\sigma,\gamma_i)=\delta(c,\sigma,\gamma_i)\cup\{(q,\gamma_j)\}
 
 
 
 
This algorithm will produce a valid PDA and will run in time O(n), where n is the length of the code.
----
Since any SPPDA can be converted into PDA-er code, and since any valid PDA-er code can be converted into a SPPDA, PDA-er must have the computational power of a SPPDA. Since a SPPDA has the same computational power as a PDA, PDA-er must have the computational power of a PDA.
Category:Proofs
Category:2021