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.