Nondeterministic Finite Automata (NFA)

A nondeterministic finite automation is a mathematical model consists of

1. a set of states S;
2. a set of input symbol, ∑, called the input symbols alphabet.
3. a transition function move that maps state-symbol pairs to sets of states.
4. a state so called the initial or the start state.
5. a set of states F called the accepting or final state.

An NFA can be described by a transition graph (labeled graph) where the nodes are states and the edges shows the transition function.

The labeled on each edge is either a symbol in the set of  alphabet, ∑, or denoting empty string.

Following figure shows an NFA that recognizes the language: (a | b)* a bb.

FIGURE 3.19 - pp 114

This automation is nondeterministic because when it is in state-0 and the input symbol is a, it can either go to state-1 or stay in state-0.

The transition is

FIGURE 115 pp. 115

The advantage of transition table is that it provides fast access to the transitions of states and the disadvantage is that it can take up a lot of soace.

The following diagram shows the move made in accepting the input strings abb, aabb and ba bb.

abb :

In general, more than one sequence of moves can lead to an accepting state. If at least one such move ended up in a final state. For instance

The language defined by an NFA is the set of input strings that particular NFA accepts.

Following figure shows an NFA that recognize aa* | bb*.

Note that 's disappear in a cancatenation.

FIGURE 3.21 pp. 116

The transition table is: