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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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$, Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{f}} would not need to be expressed in the code, and neither would every transition to Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{0}=\mathrm {NULL} } , let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{0}=q}
     2. If $q\notin Q$, let $Q=Q\cup \{q\}$
     3. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\notin F} , let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F=F\cup \{q\}}
     4. Let $c=q$
  2. If we encounter code of the form .[$q$].:
     1. If $q_{0}=\mathrm {NULL}$, let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{0}=q}
     2. If $q\notin Q$, let $Q=Q\cup \{q\}$
     3. If $q\in F$, let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F=F-\{q\}}
     4. Let $c=q$
  3. If we encounter code of the form -[$\sigma$]-[$q$]-:
     1. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \sigma \notin \Sigma } , let $\Sigma =\Sigma \cup \{\sigma \}$
     2. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Q=Q\cup \{q_{f}\}}
• For every Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (q,\sigma )\in Q\times \Sigma } :
  1. If $\delta (q,\sigma )$ is undefined, let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (q,\sigma )=q_{f}}

This algorithm will produce a valid DFA, since it will have a $\delta$ that is defined for every possible Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |Q|\leq n} and Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\Sigma |\leq n} . Therefore, the running time, expressed solely with respect to the input (the code), is Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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.