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$ $\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}\}$ $q_{i}\in Q-\{q_{0}\}$ :
1. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{i}\in F} write ..[Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{i}} ]., otherwise write .[ $q_{i}$ ].
2. For each symbol $\sigma \in \Sigma$ $\sigma \in \Sigma$ :
  1. Let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\in F} , it will be accepting, since it will be written as ..[ $q$ ]., and for every Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p\in Q-F} , it will be failing, since it will be written as .[ $p$ ].. Because $M$ is a DFA, we know that Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (d,\sigma )} is defined for all Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \delta (q,\sigma )} in Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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}} Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M=(Q=\{\},\Sigma =\{\},\delta =\{\},q_{0}=\mathrm {NULL} ,F=\{\})}
Let Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $q_{0}=q$
  2. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\notin 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\}}
  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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q_{0}=\mathrm {NULL} } , let $q_{0}=q$
  2. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\notin 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\}}
  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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Q=Q\cup \{c\}}
  3. If Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\notin 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\}}
  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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 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 Failed to parse (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle O(|Q|\cdot |\Sigma |)\leq O(n^{2})} because $|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.

DFA-er Finite State Automaton Proof

Navigation menu

Search