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:
 
 Let q_j=\delta(q_0,\sigma)
 Write -[\sigma]-[q_j]-
 
 
 For each state q_i\in Q-\{q_0\}:
 
 If q_i\in F write ..[q_i]., otherwise write .[q_i].
 For each symbol \sigma\in\Sigma:
 
 Let q_j=\delta(q_i,\sigma)
 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 !):
 
 If we encounter code of the form ..[q].:
 
 If q_0=\mathrm{NULL}, let q_0=q
 If q\notin Q, let Q=Q\cup\{q\}
 If q\notin F, let F=F\cup\{q\}
 Let c=q
 
 
 If we encounter code of the form .[q].:
 
 If q_0=\mathrm{NULL}, let q_0=q
 If q\notin Q, let Q=Q\cup\{q\}
 If q\in F, let F=F-\{q\}
 Let c=q
 
 
 If we encounter code of the form -[\sigma]-[q]-:
 
 If \sigma\notin\Sigma, let \Sigma=\Sigma\cup\{\sigma\}
 If c\notin Q, let Q=Q\cup\{c\}
 If q\notin Q, let Q=Q\cup\{q\}
 Let \delta(c,\sigma)=q
 
 
 
 
 Let Q=Q\cup\{q_f\}
 For every (q,\sigma)\in Q\times\Sigma:
 
 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.
Category:Proofs
Category:2021