Nondeterministic Finite Automaton

We have seen that in a transition graphs a strings of input may trace the machine on several different paths depending on the choice of grouping (Inputs). Human choice becomes the big factor in selecting the path since machine does not make all its own determinations. So we say that this machine is nondeterministic.

In 1959, Michael Oser Rabin and Dana Scott may introduce the Nondeterminisam Finite Automata for Language-recognizing.

A nondeterministic finite automaton (NFA) is a collection of three things:

1. A finite set of states with at least one start state and some of the final states.

2. An alphabet Σ for possible input letters.

3. A finite set of transitions which show the transition from one state to other along with input labelled edges except null.

Since every deterministic finite automaton is a example of NFA. So we have:

1. Every NFA is an FA.

2. Every NFA has an equivalent Transition Graph.

3. Every TG has an equivalent FA, by Kleene’s Theorem.

Therefore:

NFA = FA
Or, languages of NFA is subset of languages of DFA is subset of languages of TG’s = languages of DFA

Rule 1:
DFA =NFA

Or FA = NFA

Rule 2:
Any language defined by a nondeterministic finite automaton is also defined by a deterministic automaton or in other words they are of equal power.

The equation FA = NFA means that every NFA is itself a FA is not true but it says that for every NFA there is some FA or DFA that is equivalent to NFA as a language acceptor.

NFA is sometimes easier to use in place of FA to define a given language.

Example:
A machine which combines two FA’s; one accepts the language of a regular expression r1 and other one accepts the language of regular expression r2.

If Start states in both of two machines have no one edges coming into them, then we produce a NFA which accepts exactly the language of r1+r2.


Non-Deterministic Finite Automaton in PDF:
Nondeterministic Finite Automaton