First, we show that we can convert any DFA into DFA-er code. Suppose we are given a deterministic finite automaton
, where
is the set of states,
is the set of input symbols,
is the transition function,
is the initial state, and
is the set of accepting states.
Let [
]
denote the binary representation of
. To convert
to DFA-er code, we use the following algorithm:
- If
write ..[
].
, otherwise write .[
].
- For each symbol
:
- Let

- Write
-[
]-[
]-
- For each state
:
- If
write ..[
].
, otherwise write .[
].
- For each symbol
:
- Let

- Write
-[
]-[
]-
- Write
!
The code created by this process will have
as a starting state, since it is the first state specified. For every
, it will be accepting, since it will be written as ..[
].
, and for every
, it will be failing, since it will be written as .[
].
. Because
is a DFA, we know that
is defined for all
and all
. We therefore know that every transition of
will be encoded, since we iterate through all
and all
, encoding the proper transition. Therefore, the code correctly encodes
.
Assuming that we can look up
in
time, this algorithm runs in time
, since we iterate through each
, and for each state, we iterate through each
. 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
. It is possible that a shorter DFA-er representation of
exists, however, since many DFAs include a "fail state," meaning a state
for which
. Since DFA-er does not require that every state have a defined transition for every symbol in
,
would not need to be expressed in the code, and neither would every transition to
.
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

- Let

- While there is still code to read (i.e., we have not yet encountered a
!
):
- If we encounter code of the form
..[
].
:
- If
, let 
- If
, let 
- If
, let 
- Let

- If we encounter code of the form
.[
].
:
- If
, let 
- If
, let 
- If
, let 
- Let

- If we encounter code of the form
-[
]-[
]-
:
- If
, let 
- If
, let 
- If
, let 
- Let

- Let

- For every
:
- If
is undefined, let 
This algorithm will produce a valid DFA, since it will have a
that is defined for every possible
; either going to the state given by the code, or to
(the failing state) if it is not specified.
This algorithm will run in time
, where
is the length of the code. We also know that
because
and
. Therefore, the running time, expressed solely with respect to the input (the code), is
.
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.