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\geq 2$:
  1. Create $n-1$ new states $\{q_{1},q_{2},\dots ,q_{n-2},q_{n-1}\}\in Q'-F$
  2. Let $\delta '(q_{i},\sigma ,\gamma )=\{(q_{1},\gamma _{1})\}$
  3. For $k\in \{2,\dots ,n-1\}$, let $\delta '(q_{k-1},\epsilon ,\epsilon )=\{(q_{k},\gamma _{i})\}$
  4. 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$:
  1. 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}\}$:
  1. If $q_{i}\in F$ write ..[$q_{i}$]., otherwise write .[$q_{i}$].
  2. For each $(\sigma ,\gamma _{j})\in (\Sigma \cup \{\epsilon \})\times \Gamma$:
     1. 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 !):
  1. If we encounter code of the form ..[$q$].:
     1. If $q_{0}=\mathrm {NULL}$, let $q_{0}=q$
     2. If $q\notin Q$, let $Q=Q\cup \{q\}$
     3. If $q\notin F$, let $F=F\cup \{q\}$
     4. Let $c=q$
  2. If we encounter code of the form .[$q$].:
     1. If $q_{0}=\mathrm {NULL}$, let $q_{0}=q$
     2. If $q\notin Q$, let $Q=Q\cup \{q\}$
     3. If $q\in F$, let $F=F-\{q\}$
     4. Let $c=q$
  3. If we encounter code of the form -[$\sigma$]-[$\gamma _{i}$]-[$\gamma _{j}$]-[$q$]-:
     1. If $\sigma \notin \Sigma$, let $\Sigma =\Sigma \cup \{\sigma \}$
     2. If $\gamma _{i}\notin \Gamma$, let $\Gamma =\Gamma \cup \{\gamma _{i}\}$
     3. If $\gamma _{j}\notin \Gamma$, let $\Gamma =\Gamma \cup \{\gamma _{j}\}$
     4. If $c\notin Q$, let $Q=Q\cup \{c\}$
     5. If $q\notin Q$, let $Q=Q\cup \{q\}$
     6. 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.