# 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 $M=(Q,\Sigma ,\delta ,q_{0},F)$ , where $Q$ is the set of states, $\Sigma$ is the set of input symbols, $\delta :Q\times \Sigma \to Q$ is the transition function, $q_{0}\in Q$ is the initial state, and $F\subseteq Q$ is the set of accepting states.

Let [$x$ ] denote the binary representation of $x\in Q\cup \Sigma$ . To convert $M$ to DFA-er code, we use the following algorithm:

• If $q_{0}\in F$ write ..[$q_{0}$ ]., otherwise write .[$q_{0}$ ].
• For each symbol $\sigma \in \Sigma$ :
1. Let $q_{j}=\delta (q_{0},\sigma )$ 2. Write -[$\sigma$ ]-[$q_{j}$ ]-
• For each state $q_{i}\in Q-\{q_{0}\}$ :
1. If $q_{i}\in F$ write ..[$q_{i}$ ]., otherwise write .[$q_{i}$ ].
2. For each symbol $\sigma \in \Sigma$ :
1. Let $q_{j}=\delta (q_{i},\sigma )$ 2. Write -[$\sigma$ ]-[$q_{j}$ ]-
• Write !

The code created by this process will have $q_{0}$ as a starting state, since it is the first state specified. For every $q\in F$ , it will be accepting, since it will be written as ..[$q$ ]., and for every $p\in Q-F$ , it will be failing, since it will be written as .[$p$ ].. Because $M$ is a DFA, we know that $\delta (d,\sigma )$ is defined for all $q\in Q$ and all $\sigma \in \Sigma$ . We therefore know that every transition of $M$ will be encoded, since we iterate through all $q\in Q$ and all $\sigma \in \Sigma$ , encoding the proper transition. Therefore, the code correctly encodes $M$ .

Assuming that we can look up $\delta (q,\sigma )$ in $O(1)$ time, this algorithm runs in time $O(|Q|\cdot |\Sigma |)$ , since we iterate through each $q\in Q$ , and for each state, we iterate through each $\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 $\delta$ . It is possible that a shorter DFA-er representation of $M$ exists, however, since many DFAs include a "fail state," meaning a state $q_{f}\notin F$ for which $\delta (q_{f},\sigma )=q_{f}$ $\forall \sigma \in \Sigma$ . Since DFA-er does not require that every state have a defined transition for every symbol in $\Sigma$ , $q_{f}$ would not need to be expressed in the code, and neither would every transition to $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 $M=(Q=\{\},\Sigma =\{\},\delta =\{\},q_{0}=\mathrm {NULL} ,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$ ]-[$q$ ]-:
1. If $\sigma \notin \Sigma$ , let $\Sigma =\Sigma \cup \{\sigma \}$ 2. If $c\notin Q$ , let $Q=Q\cup \{c\}$ 3. If $q\notin Q$ , let $Q=Q\cup \{q\}$ 4. Let $\delta (c,\sigma )=q$ • Let $Q=Q\cup \{q_{f}\}$ • For every $(q,\sigma )\in Q\times \Sigma$ :
1. If $\delta (q,\sigma )$ is undefined, let $\delta (q,\sigma )=q_{f}$ This algorithm will produce a valid DFA, since it will have a $\delta$ that is defined for every possible $(q,\sigma )\in Q\times \Sigma$ ; either going to the state given by the code, or to $q_{f}$ (the failing state) if it is not specified.

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