# 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 ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$, where ${\displaystyle Q}$ is the set of states, ${\displaystyle \Sigma }$ is the set of input symbols, ${\displaystyle \delta :Q\times \Sigma \to Q}$ is the transition function, ${\displaystyle q_{0}\in Q}$ is the initial state, 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 }$. To convert ${\displaystyle M}$ to DFA-er code, we use the following algorithm:

• If ${\displaystyle q_{0}\in F}$ write ..[${\displaystyle q_{0}}$]., otherwise write .[${\displaystyle q_{0}}$].
• For each symbol ${\displaystyle \sigma \in \Sigma }$:
1. Let ${\displaystyle q_{j}=\delta (q_{0},\sigma )}$
2. Write -[${\displaystyle \sigma }$]-[${\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 symbol ${\displaystyle \sigma \in \Sigma }$:
1. Let ${\displaystyle q_{j}=\delta (q_{i},\sigma )}$
2. Write -[${\displaystyle \sigma }$]-[${\displaystyle q_{j}}$]-
• Write !

The code created by this process will have ${\displaystyle q_{0}}$ as a starting state, since it is the first state specified. 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 DFA, we know that ${\displaystyle \delta (d,\sigma )}$ is defined for all ${\displaystyle q\in Q}$ and all ${\displaystyle \sigma \in \Sigma }$. We therefore know that every transition of ${\displaystyle M}$ will be encoded, since we iterate through all ${\displaystyle q\in Q}$ and all ${\displaystyle \sigma \in \Sigma }$, encoding the proper transition. Therefore, the code correctly encodes ${\displaystyle M}$.

Assuming that we can look up ${\displaystyle \delta (q,\sigma )}$ in ${\displaystyle O(1)}$ time, this algorithm runs in time ${\displaystyle O(|Q|\cdot |\Sigma |)}$, since we iterate through each ${\displaystyle q\in Q}$, and for each state, we iterate through each ${\displaystyle \sigma \in \Sigma }$. 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 ${\displaystyle \delta }$. It is possible that a shorter DFA-er representation of ${\displaystyle M}$ exists, however, since many DFAs include a "fail state," meaning a state ${\displaystyle q_{f}\notin F}$ for which ${\displaystyle \delta (q_{f},\sigma )=q_{f}}$ ${\displaystyle \forall \sigma \in \Sigma }$. Since DFA-er does not require that every state have a defined transition for every symbol in ${\displaystyle \Sigma }$, ${\displaystyle q_{f}}$ would not need to be expressed in the code, and neither would every transition to ${\displaystyle q_{f}}$.

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 ${\displaystyle M=(Q=\{\},\Sigma =\{\},\delta =\{\},q_{0}=\mathrm {NULL} ,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 q}$]-:
1. If ${\displaystyle \sigma \notin \Sigma }$, let ${\displaystyle \Sigma =\Sigma \cup \{\sigma \}}$
2. If ${\displaystyle c\notin Q}$, let ${\displaystyle Q=Q\cup \{c\}}$
3. If ${\displaystyle q\notin Q}$, let ${\displaystyle Q=Q\cup \{q\}}$
4. Let ${\displaystyle \delta (c,\sigma )=q}$
• Let ${\displaystyle Q=Q\cup \{q_{f}\}}$
• For every ${\displaystyle (q,\sigma )\in Q\times \Sigma }$:
1. If ${\displaystyle \delta (q,\sigma )}$ is undefined, let ${\displaystyle \delta (q,\sigma )=q_{f}}$

This algorithm will produce a valid DFA, since it will have a ${\displaystyle \delta }$ that is defined for every possible ${\displaystyle (q,\sigma )\in Q\times \Sigma }$; either going to the state given by the code, or to ${\displaystyle q_{f}}$ (the failing state) if it is not specified.

This algorithm will run in time ${\displaystyle O(n)+O(|Q|\cdot |\Sigma |)}$, where ${\displaystyle n}$ is the length of the code. We also know that ${\displaystyle O(|Q|\cdot |\Sigma |)\leq O(n^{2})}$ because ${\displaystyle |Q|\leq n}$ and ${\displaystyle |\Sigma |\leq n}$. Therefore, the running time, expressed solely with respect to the input (the code), is ${\displaystyle O(n^{2})}$.

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.