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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q\times\Gamma\cup\{\epsilon\}\}} instead of a transition function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q} is the set of states, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma} is the set of input symbols, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Gamma} is the set of stack symbols, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta:Q\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q\times\Gamma^*\}} is the transition function, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_0\in Q} is the initial state, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Z\in\Gamma} is the initial stack symbol, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F\subseteq Q} is the set of accepting states, we may form a SPPDA Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M'=(Q',\Sigma,\Gamma,\delta',q_0,Z,F)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q'\supseteq Q} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta':Q'\times(\Sigma\cup\{\epsilon\})\times\Gamma\to A=\{x:x\in Q'\times\Gamma\cup\{\epsilon\}\}} , that behaves identically to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} .

The process is as follows:

• For every transition Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} has of the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (q_j,w)\in\delta(q_i,\sigma,\gamma)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w=\gamma_1\gamma_2\dots\gamma_n} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n\geq2} :
  1. Create Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n-1} new states Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{q_1,q_2,\dots,q_{n-2},q_{n-1}\}\in Q'-F}
  2. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta'(q_i,\sigma,\gamma)=\{(q_1,\gamma_1)\}}
  3. For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle k\in\{2,\dots,n-1\}} , let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta'(q_{k-1},\epsilon,\epsilon)=\{(q_k,\gamma_i)\}}
  4. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta'(q_{n-1},\epsilon,\epsilon)=\{(q_j,\gamma_n)\}}
• For all other transitions of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} , let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta'(q_i,\sigma,\gamma)=\delta(q_i,\sigma,\gamma)}

This means that if we run Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M'} from state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_i} on the input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sigma} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma} on the top of the stack, after 1 step, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M'} will be in state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_1} and will have pushed Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma_1} to the stack. After another step, it will be in state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_2} and will have pushed Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma_2} to the stack. This process will continue until it is in state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_{n-1}} , and after one more step it will be in state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_j} and will have pushed Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma_n} to the stack. Therefore, after Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} steps, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M'} will have moved from state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_i} to state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_j} and will have pushed Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \gamma_1\gamma_2\dots\gamma_n=w} to the stack, meaning it has the exact same behavior as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M=(Q,\Sigma,\Gamma,\delta,q_0,Z,F)} , where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q} is the set of states, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma} is the set of input symbols, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Gamma} is the set of stack symbols, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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.