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 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^*\}} 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 ---[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} ]-[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} ]-
If 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 F} write ..[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} ]., otherwise write .[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} ].
For each 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,\gamma_i)\in(\Sigma\cup\{\epsilon\})\times\Gamma} :
1. For each 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,\gamma_j)\in\delta(q_0,\sigma,\gamma_i)} , write -[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} ]-[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_i} ]-[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_j} ]-[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} ]-
For each 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\in Q-\{q_0\}} :
1. If 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\in F} write ..[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} ]., otherwise write .[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} ].
2. For each 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,\gamma_j)\in(\Sigma\cup\{\epsilon\})\times\Gamma} :
  1. For each 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_k,\gamma_k)\in\delta(q_i,\sigma,\gamma_j)} , write -[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} ]-[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_j} ]-[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_k} ]-[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_k} ]-
Write !

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

Assuming that we can look up 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,\sigma,\gamma)} in 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 O(1)} time, this algorithm runs in time 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 O(|Q|\cdot|\Sigma|\cdot|\Gamma|)} , since we iterate through each 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\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.

PDA-er Pushdown Automaton Proof

Navigation menu

Search