# PDA-er Pushdown Automaton Proof

Jump to navigation Jump to search

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 ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma \to A=\{x:x\in Q\times \Gamma \cup \{\epsilon \}\}}$ instead of a transition function ${\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 ${\displaystyle \Gamma ^{*}}$: the words of length 0 or 1. The other direction requires more work.

Formally, given any PDA ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)}$ where ${\displaystyle Q}$ is the set of states, ${\displaystyle \Sigma }$ is the set of input symbols, ${\displaystyle \Gamma }$ is the set of stack symbols, ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma \to A=\{x:x\in Q\times \Gamma ^{*}\}}$ is the transition function, ${\displaystyle q_{0}\in Q}$ is the initial state, ${\displaystyle Z\in \Gamma }$ is the initial stack symbol, and ${\displaystyle F\subseteq Q}$ is the set of accepting states, we may form a SPPDA ${\displaystyle M'=(Q',\Sigma ,\Gamma ,\delta ',q_{0},Z,F)}$, where ${\displaystyle Q'\supseteq Q}$ and ${\displaystyle \delta ':Q'\times (\Sigma \cup \{\epsilon \})\times \Gamma \to A=\{x:x\in Q'\times \Gamma \cup \{\epsilon \}\}}$, that behaves identically to ${\displaystyle M}$.

The process is as follows:

• For every transition ${\displaystyle M}$ has of the form ${\displaystyle (q_{j},w)\in \delta (q_{i},\sigma ,\gamma )}$, where ${\displaystyle w=\gamma _{1}\gamma _{2}\dots \gamma _{n}}$ and ${\displaystyle n\geq 2}$:
1. Create ${\displaystyle n-1}$ new states ${\displaystyle \{q_{1},q_{2},\dots ,q_{n-2},q_{n-1}\}\in Q'-F}$
2. Let ${\displaystyle \delta '(q_{i},\sigma ,\gamma )=\{(q_{1},\gamma _{1})\}}$
3. For ${\displaystyle k\in \{2,\dots ,n-1\}}$, let ${\displaystyle \delta '(q_{k-1},\epsilon ,\epsilon )=\{(q_{k},\gamma _{i})\}}$
4. Let ${\displaystyle \delta '(q_{n-1},\epsilon ,\epsilon )=\{(q_{j},\gamma _{n})\}}$
• For all other transitions of ${\displaystyle M}$, let ${\displaystyle \delta '(q_{i},\sigma ,\gamma )=\delta (q_{i},\sigma ,\gamma )}$

This means that if we run ${\displaystyle M'}$ from state ${\displaystyle q_{i}}$ on the input ${\displaystyle \sigma }$ with ${\displaystyle \gamma }$ on the top of the stack, after 1 step, ${\displaystyle M'}$ will be in state ${\displaystyle q_{1}}$ and will have pushed ${\displaystyle \gamma _{1}}$ to the stack. After another step, it will be in state ${\displaystyle q_{2}}$ and will have pushed ${\displaystyle \gamma _{2}}$ to the stack. This process will continue until it is in state ${\displaystyle q_{n-1}}$, and after one more step it will be in state ${\displaystyle q_{j}}$ and will have pushed ${\displaystyle \gamma _{n}}$ to the stack. Therefore, after ${\displaystyle n}$ steps, ${\displaystyle M'}$ will have moved from state ${\displaystyle q_{i}}$ to state ${\displaystyle q_{j}}$ and will have pushed ${\displaystyle \gamma _{1}\gamma _{2}\dots \gamma _{n}=w}$ to the stack, meaning it has the exact same behavior as ${\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 ${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)}$, where ${\displaystyle Q}$ is the set of states, ${\displaystyle \Sigma }$ is the set of input symbols, ${\displaystyle \Gamma }$ is the set of stack symbols, ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma \to A=\{x:x\in Q\times \Gamma \cup \{\epsilon \}\}}$ is the transition function, ${\displaystyle q_{0}\in Q}$ is the initial state, ${\displaystyle Z\in \Gamma }$ is the initial stack symbol, and ${\displaystyle F\subseteq Q}$ is the set of accepting states.

Let [${\displaystyle x}$] denote the binary representation of ${\displaystyle x\in Q\cup \Sigma \cup \Gamma \cup \{\epsilon \}}$ (note that [${\displaystyle \epsilon }$] is equivalent to an empty character). To convert ${\displaystyle M}$ to PDA-er code, we use the following algorithm:

• For some ${\displaystyle q_{-1}\notin Q}$, write .[${\displaystyle q_{-1}}$].
• Write ---[${\displaystyle Z}$]-[${\displaystyle q_{0}}$]-
• If ${\displaystyle q_{0}\in F}$ write ..[${\displaystyle q_{0}}$]., otherwise write .[${\displaystyle q_{0}}$].
• For each ${\displaystyle (\sigma ,\gamma _{i})\in (\Sigma \cup \{\epsilon \})\times \Gamma }$:
1. For each ${\displaystyle (q_{j},\gamma _{j})\in \delta (q_{0},\sigma ,\gamma _{i})}$, write -[${\displaystyle \sigma }$]-[${\displaystyle \gamma _{i}}$]-[${\displaystyle \gamma _{j}}$]-[${\displaystyle q_{j}}$]-
• For each state ${\displaystyle q_{i}\in Q-\{q_{0}\}}$:
1. If ${\displaystyle q_{i}\in F}$ write ..[${\displaystyle q_{i}}$]., otherwise write .[${\displaystyle q_{i}}$].
2. For each ${\displaystyle (\sigma ,\gamma _{j})\in (\Sigma \cup \{\epsilon \})\times \Gamma }$:
1. For each ${\displaystyle (q_{k},\gamma _{k})\in \delta (q_{i},\sigma ,\gamma _{j})}$, write -[${\displaystyle \sigma }$]-[${\displaystyle \gamma _{j}}$]-[${\displaystyle \gamma _{k}}$]-[${\displaystyle q_{k}}$]-
• Write !

The code created by this process will have ${\displaystyle q_{-1}}$ as a starting state, since it is the first state specified. However, the only valid transition from ${\displaystyle q_{-1}}$ is ${\displaystyle \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 ${\displaystyle q_{0}}$ and have ${\displaystyle Z}$ on the stack; in other words, it will be in the same position ${\displaystyle M}$ is at step 0. For every ${\displaystyle q\in F}$, it will be accepting, since it will be written as ..[${\displaystyle q}$]., and for every ${\displaystyle p\in Q-F}$, it will be failing, since it will be written as .[${\displaystyle p}$].. Because ${\displaystyle M}$ is a PDA, we know that ${\displaystyle \delta (q,\sigma ,\gamma )}$ is not defined for all ${\displaystyle (q,\sigma ,\gamma )\in Q\times (\Sigma \cup \{\epsilon \})\times \Gamma }$. We therefore know that every transition of ${\displaystyle M}$ will be encoded, since we iterate through all ${\displaystyle (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 ${\displaystyle M}$.

Assuming that we can look up ${\displaystyle \delta (q,\sigma ,\gamma )}$ in ${\displaystyle O(1)}$ time, this algorithm runs in time ${\displaystyle O(|Q|\cdot |\Sigma |\cdot |\Gamma |)}$, since we iterate through each ${\displaystyle q\in Q}$, and for each state, we iterate through each ${\displaystyle (\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 ${\displaystyle M}$ is a minimal SPPDA—that is, it has no unnecessary states or transitions—this is the shortest code that completely encodes ${\displaystyle 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 ${\displaystyle M=(Q=\{\},\Sigma =\{\},\Gamma =\{\},\delta =\{\},q_{0}=\mathrm {NULL} ,Z=\epsilon ,F=\{\})}$
• Let ${\displaystyle 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 ..[${\displaystyle q}$].:
1. If ${\displaystyle q_{0}=\mathrm {NULL} }$, let ${\displaystyle q_{0}=q}$
2. If ${\displaystyle q\notin Q}$, let ${\displaystyle Q=Q\cup \{q\}}$
3. If ${\displaystyle q\notin F}$, let ${\displaystyle F=F\cup \{q\}}$
4. Let ${\displaystyle c=q}$
2. If we encounter code of the form .[${\displaystyle q}$].:
1. If ${\displaystyle q_{0}=\mathrm {NULL} }$, let ${\displaystyle q_{0}=q}$
2. If ${\displaystyle q\notin Q}$, let ${\displaystyle Q=Q\cup \{q\}}$
3. If ${\displaystyle q\in F}$, let ${\displaystyle F=F-\{q\}}$
4. Let ${\displaystyle c=q}$
3. If we encounter code of the form -[${\displaystyle \sigma }$]-[${\displaystyle \gamma _{i}}$]-[${\displaystyle \gamma _{j}}$]-[${\displaystyle q}$]-:
1. If ${\displaystyle \sigma \notin \Sigma }$, let ${\displaystyle \Sigma =\Sigma \cup \{\sigma \}}$
2. If ${\displaystyle \gamma _{i}\notin \Gamma }$, let ${\displaystyle \Gamma =\Gamma \cup \{\gamma _{i}\}}$
3. If ${\displaystyle \gamma _{j}\notin \Gamma }$, let ${\displaystyle \Gamma =\Gamma \cup \{\gamma _{j}\}}$
4. If ${\displaystyle c\notin Q}$, let ${\displaystyle Q=Q\cup \{c\}}$
5. If ${\displaystyle q\notin Q}$, let ${\displaystyle Q=Q\cup \{q\}}$
6. Let ${\displaystyle \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 ${\displaystyle O(n)}$, where ${\displaystyle 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.