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:

• an input alphabet $\Sigma$,
• a finite set S whose elements are called states,
• a set I $\subseteq$ S of distinguished states, called initial states,
• a set F $\subseteq$ S of distinguished states, called accepting states,
• a function $\delta$ from S×$\Sigma$ to 2^S, thus every state-symbol couple is mapped by $\delta$ to a subset of S,
• a function $\tau$ mapping each state of S to a subset of S

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.

INSTANTANEOUS TRANSITIONS.

Observe that

• The goal of the function $\tau$ is to describe transitions from one state to others without reading any letter. One can view also these $\varepsilon$-transitions from one state to others as transitions obtained after reading the empty word $\varepsilon$.
• In the transition graph of a NFAIT the $\varepsilon$-transitions are indicated by edges (from one state to another) labeled by $\varepsilon$.

Figure 8: A NFAIT accepting L₁  $\cup$  L₂  $\cup$  L₃  $\cup$  L₄.

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:

• if w = $\varepsilon$ we have s$\;\stackrel{{w}}{{\rightarrow}}\;$s' for every s' $\in$ $\overline{{{\tau}}}$({s}),
• if w = vx where v is a word and x is a letter, we have s$\;\stackrel{{vx}}{{\rightarrow}}\;$s''' if there exist s', s'' such that s$\;\stackrel{{v}}{{\rightarrow}}\;$s', s'' $\in$ $\delta$(s', x) and s''' $\in$ $\overline{{{\tau}}}$({s''}).

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 initial state is $\overline{{{\tau}}}$(I) instead of $\overline{{I}}$.
• The transition $\Delta$(A, x) is defined by:
  $$\Delta$$(A, x)  =  $$\overline{{{\tau}}}$$({s' | ($$\exists$$s $$\in$$ A) (s' $$\in$$ $$\delta$$(s, x))}).

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.

REMARKS ABOUT THE NFAIT-TO-DFA CONSTRUCTION.

• If the input NFAIT (of the subset algorithm) has q states then the output DFA has $\cal {O}$(2^q) states.
• However the states of the DFA computed by this algorithm have the following property: they can all be reached on some input word. In other words, none of these computed states is useless.
• In practice, the number of reachable states (of the output DFA) is much smaller than the above exponential upper bound.
• However the DFA constructed by the above algorithm is not necessarily minimal: it is possible that the number of states can be further reduced. Figure 10 shows a DFA recognizing the same language as the DFA of Figure 4 but using 6 states instead of 9.

Figure 10: A minimal DFA accepting L₁  $\cup$  L₂  $\cup$  L₃  $\cup$  L₄.