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
![{\displaystyle q_{j}=\delta (q_{0},\sigma )}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f632cb249914753883a60d4a5ed7b05ebeec2cfd)
- Write
-[
]-[
]-
- For each state
:
- If
write ..[
].
, otherwise write .[
].
- For each symbol
:
- Let
![{\displaystyle q_{j}=\delta (q_{i},\sigma )}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/c5abe900071eb29928a9e205e9ea4a4e4e0e820d)
- 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
![{\displaystyle M=(Q=\{\},\Sigma =\{\},\delta =\{\},q_{0}=\mathrm {NULL} ,F=\{\})}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/cc7c0b1e183f14b77c6430a48e5167a11b9420d4)
- Let
![{\displaystyle c=0}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d9ee918699d0cb4b8c633cc1f520a8a7a174f44a)
- While there is still code to read (i.e., we have not yet encountered a
!
):
- If we encounter code of the form
..[
].
:
- If
, let ![{\displaystyle q_{0}=q}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/99ebdd37c539c9589f947666fe023325949038d7)
- If
, let ![{\displaystyle Q=Q\cup \{q\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2fd2425ba03ae35596eae1b360fe8d10b387c38f)
- If
, let ![{\displaystyle F=F\cup \{q\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f263f04ab3e7d17b330e899a977bb2c9a85fed94)
- Let
![{\displaystyle c=q}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/32e8229e4f4062ac62a099f67a7c7af684651152)
- If we encounter code of the form
.[
].
:
- If
, let ![{\displaystyle q_{0}=q}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/99ebdd37c539c9589f947666fe023325949038d7)
- If
, let ![{\displaystyle Q=Q\cup \{q\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2fd2425ba03ae35596eae1b360fe8d10b387c38f)
- If
, let ![{\displaystyle F=F-\{q\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/8510ae3c4e63fa1b69c2db15c4032a512e4b5974)
- Let
![{\displaystyle c=q}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/32e8229e4f4062ac62a099f67a7c7af684651152)
- If we encounter code of the form
-[
]-[
]-
:
- If
, let ![{\displaystyle \Sigma =\Sigma \cup \{\sigma \}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/e7ebac8190589c661aa4bc1eac382a5a89cb32f0)
- If
, let ![{\displaystyle Q=Q\cup \{c\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ae0985fb5c688f70a4321e16e10e8ac1d3ab5f53)
- If
, let ![{\displaystyle Q=Q\cup \{q\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2fd2425ba03ae35596eae1b360fe8d10b387c38f)
- Let
![{\displaystyle \delta (c,\sigma )=q}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/185a361a662e829ed758bc4a57b4afa933c01466)
- Let
![{\displaystyle Q=Q\cup \{q_{f}\}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b581408182287c265e2ffaae302694c1760937db)
- For every
:
- If
is undefined, let ![{\displaystyle \delta (q,\sigma )=q_{f}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/bebc8dfcd3bba259eacf3ff3ed72c0936f71207d)
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.