A recognizer for a language is a program that takes a string x as input and answers “yes” if x is a sentence of the language and “no” otherwise. One can compile any regular expression into a recognizer by constructing a generalized transition diagram called finite automation. Finite automation can be deterministic means that more than one transition out of a state may be possible on the same input symbol. Both automata are capable of recognizing what regular expression can denote.
Define Nondeterministic Finite Automata (NFA).
A nondeterministic finite automaton is a mathematical model consists of
- a set of states Q.
- a set of input symbols, L called the input symbols alphabet.
- a transition function move that maps state-symbol pairs to sets of states.
- a state so-called the initial or the start state.
- 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 show the transition function. The labeled on each edge is either a symbol in the set of the alphabet or denoting an empty string. The following figure shows an NFA that recognizes the language: (10)* I (01)*
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 advantage of the 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 space.
The language defined by an NFA is the set of input strings that a particular NFA accepts.
NFA Example: NFA for 1(1 * O)*0.