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 -transitions) consists of six things:

• an input alphabet ,
• a finite set S whose elements are called states,
• a set I S of distinguished states, called initial states,
• a set F S of distinguished states, called accepting states,
• a function from S× to 2S, thus every state-symbol couple is mapped by to a subset of S,
• a function mapping each state of S to a subset of S
such that (, S, I, T,) is a NFA. The functions and are called the non-instaneous transition function and the -transition function (or the instaneous transition function). Such an automaton will be called a NFAIT or an -NFA, for short.

INSTANTANEOUS TRANSITIONS.

Observe that

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

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

Algorithm 2
1
toSee := A;
2
(A) := A;
3
while toSee repeat
3.1
s := first(toSee); toSee := rest(toSee);
3.2
for s' (s) repeat
3.2.1
if (s' toSee) and (s' (A)) then toSee := cons(s', toSee);
3.3
(A) := cons( s,(A));
4
return( (A))

For two states s and s', and for a word w we define the relation ss' by induction on the length | w| of w:

• if w = we have ss' for every s' ({s}),
• if w = vx where v is a word and x is a letter, we have ss''' if there exist s', s'' such that ss', s'' (s', x) and s''' ({s''}).
a word w over is accepted (or recognized) by the NFAIT if there exists an initial state i and a final state f such that if.

FROM A NFAIT TO A DFA ACCEPTING THE SAME LANGUAGE.

Theorem 2   Let = (, S, I, T,,) be a NFAIT and let L be the language accepted by . Then there exists a DFA which accepts L too.

To construct such an one proceeds as in Algorithm 1 with the following two modifications.

• The initial state is (I) instead of .
• The transition (A, x) is defined by:

(A, x)  =  ({s' | (s A) (s' (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 (I) = (1) = 134. The transitions from it are (134, a) = 2, (134, b) = (134, c) = . This shows that and 2 are states of the output DFA. The 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 (2, a) = 2, (2, b) = 1234 (2, c) = 1234. This shows that 1234 is a state of the output DFA.
3.
The transition from state 1234 are (1234, a) = 2, (1234, b) = 1234 (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 2 2 1234 1234 1234 2 1234 1234