A nondeterministic finite automation is a mathematical model consists of
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.
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: