next up previous
Next: Finite Automata. Up: Finite Automata Previous: Non-deterministic Finite Automata

Non-deterministic Finite Automata with instantaneous transitions

NFA WITH INSTANTANEOUS TRANSITIONS. A non-deterministic finite automaton with instantaneous transitions (or $ \varepsilon$-transitions) consists of six things:

such that ($ \Sigma$, S, I, T,$ \delta$) is a NFA. The functions $ \delta$ and $ \tau$ are called the non-instaneous transition function and the $ \varepsilon$-transition function (or the instaneous transition function). Such an automaton will be called a NFAIT or an $ \varepsilon$-NFA, for short.
Figure 7: A non-deterministic finite automaton with instantaneous transitions.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.5]{DFAandNFAIT-1.eps}
\end{figure}


INSTANTANEOUS TRANSITIONS.

Observe that

Figure 8: A NFAIT accepting L1  $ \cup$  L2  $ \cup$  L3  $ \cup$  L4.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.4]{1epsilonAutomatonFor4.eps}
\end{figure}


THE LANGUAGE ACCEPTED BY A NFAIT. For A $ \subseteq$ S we define the $ \varepsilon$-closure of A as the set of the states that can be reached from a state of A by reading the empty word $ \varepsilon$. The $ \varepsilon$-closure of A is denoted by $ \overline{{{\tau}}}$(A) and is formally defined by Algorithm 2.

Algorithm 2  
1
toSee := A;
2
$ \overline{{{\tau}}}$(A) := A;
3
while toSee $ \neq$ $ \emptyset$ repeat
3.1
s := first(toSee); toSee := rest(toSee);
3.2
for s' $ \in$ $ \tau$(s) repeat
3.2.1
if (s' $ \notin$toSee) and (s' $ \notin$$ \overline{{{\tau}}}$(A)) then toSee := cons(s', toSee);
3.3
$ \overline{{{\tau}}}$(A) := cons( s,$ \overline{{{\tau}}}$(A));
4
return( $ \overline{{{\tau}}}$(A))

For two states s and s', and for a word w we define the relation s$ \;\stackrel{{w}}{{\rightarrow}}\;$s' by induction on the length | w| of w:

a word w over $ \Sigma$ is accepted (or recognized) by the NFAIT $ \cal {A}$ if there exists an initial state i and a final state f such that i$ \;\stackrel{{w}}{{\rightarrow}}\;$f.


FROM A NFAIT TO A DFA ACCEPTING THE SAME LANGUAGE.

Theorem 2   Let $ \cal {A}$ = ($ \Sigma$, S, I, T,$ \delta$,$ \tau$) be a NFAIT and let L be the language accepted by $ \cal {A}$. Then there exists a DFA $ \overline{{\cal A}}$ which accepts L too.

To construct such an $ \overline{{\cal A}}$ one proceeds as in Algorithm 1 with the following two modifications.

The resulting algorithm is called again the subset algorithm. Figure 9 shows a DFA accepting the same language as the NFAIT of Figure 7. This DFA is computed by means of the subset algorithm. Let us describe the construction of the transition table of this DFA.
1.
The initial state is the $ \overline{{{\tau}}}$(I) = $ \overline{{{\tau}}}$(1) = 134. The transitions from it are $ \Delta$(134, a) = 2, $ \Delta$(134, b) = $ \emptyset$ $ \Delta$(134, c) = $ \emptyset$. This shows that $ \emptyset$ and 2 are states of the output DFA. The $ \emptyset$ has to be understood as the error-state. If we do not need to produce a complete DFA then we can discard this error-state.
2.
The transition from state 2 are $ \Delta$(2, a) = 2, $ \Delta$(2, b) = 1234 $ \Delta$(2, c) = 1234. This shows that 1234 is a state of the output DFA.
3.
The transition from state 1234 are $ \Delta$(1234, a) = 2, $ \Delta$(1234, b) = 1234 $ \Delta$(1234, c) = 1234.
4.
The final states of this DFA are its states which contain at least one of the final states of the input NFA. Hence the final states are 134 and 1234. Therefore we obtain the following transition table.
  a b c
134 2 $ \emptyset$ $ \emptyset$
2 2 1234 1234
1234 2 1234 1234
Figure 9: From a NFAIT to a DFA accepting the same language and produced by the subset algorithm.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.4]{DFAandNFAIT-3.eps}
\end{figure}


REMARKS ABOUT THE NFAIT-TO-DFA CONSTRUCTION.

Figure 10: A minimal DFA accepting L1  $ \cup$  L2  $ \cup$  L3  $ \cup$  L4.
\begin{figure}\htmlimage
\centering\includegraphics[scale=.5]{1minimalDFAFor4.eps}
\end{figure}



next up previous
Next: Finite Automata. Up: Finite Automata Previous: Non-deterministic Finite Automata
Marc Moreno Maza
2004-12-02