# DFA-er Finite State Automaton Proof

First, we show that we can convert any DFA into DFA-er code. Suppose we are given a deterministic finite automaton , where is the set of states, is the set of input symbols, is the transition function, is the initial state, and is the set of accepting states.

Let `[]`

denote the binary representation of . To convert to DFA-er code, we use the following algorithm:

- If write
`..[].`

, otherwise write`.[].`

- For each symbol :
- Let
- Write
`-[]-[]-`

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

, otherwise write`.[].`

- For each symbol :
- Let
- Write
`-[]-[]-`

- If write
- Write
`!`

The code created by this process will have as a starting state, since it is the first state specified. 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 DFA, we know that is defined for all and all . We therefore know that every transition of will be encoded, since we iterate through all and all , encoding the proper transition. 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 DFA-er code produced by this algorithm will encode each state once and each transition once, meaning it is the shortest code that completely encodes the transition function . It is possible that a shorter DFA-er representation of exists, however, since many DFAs include a "fail state," meaning a state for which . Since DFA-er does not require that every state have a defined transition for every symbol in , would not need to be expressed in the code, and neither would every transition to .

Next, we show that we can convert any valid DFA-er code into a DFA.

To do this, we use the following algorithm (see DFA-er's Python interpreter for a code example):

- Create a DFA
- 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
- Let

- If we encounter code of the form
- Let
- For every :
- If is undefined, let

This algorithm will produce a valid DFA, since it will have a that is defined for every possible ; either going to the state given by the code, or to (the failing state) if it is not specified.

This algorithm will run in time , where is the length of the code. We also know that because and . Therefore, the running time, expressed solely with respect to the input (the code), is .

Since any DFA can be converted to DFA-er code, and since any valid DFA-er code can be converted to a DFA, DFA-er must have the computational power of a DFA.