# 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 instead of a transition function . 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 : the words of length 0 or 1. The other direction requires more work.

Formally, given any PDA where is the set of states, is the set of input symbols, is the set of stack symbols, is the transition function, is the initial state, is the initial stack symbol, and is the set of accepting states, we may form a SPPDA , where and , that behaves identically to .

The process is as follows:

- For every transition has of the form , where and :
- Create new states
- Let
- For , let
- Let

- For all other transitions of , let

This means that if we run from state on the input with on the top of the stack, after 1 step, will be in state and will have pushed to the stack. After another step, it will be in state and will have pushed to the stack. This process will continue until it is in state , and after one more step it will be in state and will have pushed to the stack. Therefore, after steps, will have moved from state to state and will have pushed to the stack, meaning it has the exact same behavior as .

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 , where is the set of states, is the set of input symbols, is the set of stack symbols, is the transition function, is the initial state, is the initial stack symbol, and is the set of accepting states.

Let `[]`

denote the binary representation of (note that `[]`

is equivalent to an empty character). To convert to PDA-er code, we use the following algorithm:

- For some , write
`.[].`

- Write
`---[]-[]-`

- If write
`..[].`

, otherwise write`.[].`

- For each :
- For each , write
`-[]-[]-[]-[]-`

- For each , write
- For each state :
- If write
`..[].`

, otherwise write`.[].`

- For each :
- For each , write
`-[]-[]-[]-[]-`

- For each , write

- If write
- Write
`!`

The code created by this process will have as a starting state, since it is the first state specified. However, the only valid transition from is . This means that after 1 step, the PDA defined by this code will be in state and have on the stack; in other words, it will be in the same position is at step 0. For every , it will be accepting, since it will be written as `..[].`

, and for every , it will be failing, since it will be written as `.[].`

. Because is a PDA, we know that is not defined for all . We therefore know that every transition of will be encoded, since we iterate through all , encoding the proper transition if it exists, and otherwise not encoding it. Therefore, the code correctly encodes .

Assuming that we can look up in time, this algorithm runs in time , since we iterate through each , and for each state, we iterate through each . 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 is a minimal SPPDA—that is, it has no unnecessary states or transitions—this is the shortest code that completely encodes .

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
- Let
- While there is still code to read (i.e., we have not yet encountered a
`!`

):- If we encounter code of the form
`..[].`

:- If , let
- If , let
- If , let
- Let

- If we encounter code of the form
`.[].`

:- If , let
- If , let
- If , let
- Let

- If we encounter code of the form
`-[]-[]-[]-[]-`

:- If , let
- If , let
- If , let
- If , let
- If , let
- Let

- If we encounter code of the form

This algorithm will produce a valid PDA and will run in time , where 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.