Non-deterministic Finite Automata

NON-DETERMINISTIC FINITE AUTOMATA. A non-deterministic finite automaton (NFA) consists of five 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 set of states (that is a subset of S).

Observe that

• In the transition graph of a NFA the same symbol a $\in$ $\Sigma$ can label two or more transitions out of one state.
• Therefore after reading a given symbol, a NFA can have several states.

LANGUAGE RECOGNIZED BY A NFA. A word w is accepted by a NFA if after reading w the NFA is in at least one accepting state. Figure 5 shows a NFA and a DFA recognizing the same language: the language over $\Sigma$ = {a, b} consisting of the words which end with b.

Figure 5: A NFA and a DFA accepting the same language.

FROM A NFA TO A DFA ACCEPTING THE SAME LANGUAGE.

Theorem 1   Let $\cal {A}$ = ($\Sigma$, S, I, F,$\delta$) be a NFA accepting the language L. Then there exists a DFA $\overline{{{\cal A}}}$ accepting L too.

To construct such a DFA $\overline{{{\cal A}}}$ from $\cal {A}$ one proceeds as follows.

1. The alphabet is unchanged.
2. The set $\overline{{S}}$ of states of $\overline{{{\cal A}}}$ is a subset of 2^S. Hence each state of $\overline{{{\cal A}}}$ is a subset of S. The set $\overline{{S}}$ is computed by Algorithm 1 below.
3. The starting state $\overline{{I}}$ of $\overline{{{\cal A}}}$ is the set I of the initial states of $\cal {A}$.
4. The set $\overline{{F}}$ of the accepting states of $\overline{{{\cal A}}}$ is the set of the states $\overline{{s}}$ of $\overline{{S}}$ such that $\overline{{s}}$ $\cap$ F $\neq$ $\emptyset$.
5. The transition function $\Delta$ of $\overline{{{\cal A}}}$ together with $\overline{{S}}$ is determined by Algorithm 1, called the SUBSET ALGORITHM.

Algorithm 1  

1

toSee := [$\overline{{I}}$];

2

$\overline{{S}}$ := [ ];

3

while toSee $\neq$ [ ] repeat

3.1

A := first(toSee); toSee := rest(toSee);

3.2

for x $\in$ $\Sigma$ repeat

3.2.1

$\Delta$(A, x) := {s' | ($\exists$s $\in$ A) (s$\;\stackrel{{x}}{{\rightarrow}}\;$s')};

3.2.2

if ( $\Delta$(A, x) $\notin$toSee) and ( $\Delta$(A, x) $\notin$$\overline{{S}}$) then toSee := cons( $\Delta$(A, x), toSee);

3.3

$\overline{{S}}$ := cons( A,$\overline{{S}}$);

4

return( $\overline{{S}}$,$\Delta$)

In this algorithm

• toSee is the list of the states $\overline{{s}}$ of $\overline{{{\cal A}}}$ such that the $\Delta$(a,$\overline{{s}}$) for all a $\in$ $\Sigma$ have not been computed yet,
• whereas $\overline{{S}}$ contains those states $\overline{{s}}$ of $\overline{{{\cal A}}}$ for which $\Delta$(a,$\overline{{s}}$) is known for every a $\in$ $\Sigma$.
• the functions first, rest and cons operate on lists and are similar to the traditional stack routines top, pop and push respectively.

Figure 6 shows a DFA obtained from a NFA by applying Algorithm 1.

Figure 6: Another DFA accepting the same language as the previous NFA.

Remark 1   States are generally denoted with numbers. So if the states of the input NFA are called 1, 2, 3,... then the states of the output DFA could be {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, .... To simplify notation we denote the subset {i, j,...}, by ij ^... providing that there is no ambiguity.