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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta} . It is possible that a shorter DFA-er representation of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} exists, however, since many DFAs include a "fail state," meaning a state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_f\notin F} for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta(q_f,\sigma)=q_f} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \forall\sigma\in\Sigma} . Since DFA-er does not require that every state have a defined transition for every symbol in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q_f} would not need to be expressed in the code, and neither would every transition to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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 $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.