\begin{tikzpicture}
\node[state, initial, accepting] (1) {$1$};
\node[state, below left of=1] (2) {$2$};
\node[state, right of=2] (3) {$3$};
\draw (1) edge[above] node{$b$} (2)
(1) edge[below, bend right, left=0.3] node{$\epsilon$} (3)
(2) edge[loop left] node{$a$} (2)
(2) edge[below] node{$a, b$} (3)
(3) edge[above, bend right, right=0.3] node{$a$} (1);
\end{tikzpicture}
1
2 3
b
a
a, b
a
Figure 3: NFA example ([Sip12], page 57, fig 1.42)
3.5 Exponential Blow ups
Every NFA can be converted to an equivalent DFA. Prior to minimization, the DFAs have exponentially
many states compared to the corresponding NFA. Drawing those FSMs can get messy. So, here’s the final
example showing the state diagram of the DFA equivalent to the NFA N (prior to minimization). The DFA
D
2
can be described as:
D
2
= ({∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, {a, b}, δ, {1, 3}, {{1}, {1, 2}, {1, 3}, {1, 2, 3}}) ,
where δ is given by
a b
∅ ∅ ∅
{1} ∅ {2}
{2} {2, 3} {3}
{3} {1, 3} ∅
{1, 2} {2, 3} {2, 3}
{1, 3} {1, 3} {2}
{2, 3} {1, 2, 3} {3}
{1, 2, 3} {1, 2, 3} {2, 3}
.
Below is the code that generates the state diagram of the D
2
. The output is shown in figure 4.
\begin{tikzpicture}
\node[state] (phi) {$\emptyset$};
\node[state, accepting, right of=phi] (1) {$\{1\}$};
\node[state, right of=1] (2) {$\{2\}$};
\node[state, accepting, right of=2] (12) {$\{1, 2\}$};
\node[state, below of=phi] (3) {$\{3\}$};
\node[state, initial, initial where=above, accepting, right of=3] (13) {$\{1, 3\}$};
\node[state, right of=13] (23) {$\{2, 3\}$};
\node[state, accepting, right of=23] (123) {$\{1, 2, 3\}$};
5