Finite Automata
Definition of Nondeterministic Finite Automata
Subjects to be Learned
- Nondeterministic finite automata
- State transition diagram
- State transition table
Contents
In the previous section we have seen DFAs that accept some simple languages such as
, {
} ,
and { a }. As you might have noticed, those DFAs have states and transitions which
do not contribute to accepting strings and languages. For example
all we need about an FA that accepts { a } is the following regardless of the alphabet
(whether be it { a } , { a , b } or any other) .
This is so to say the essence of such an FA. But it is not DFA. A DFA that accepts { a }
would need more states and transitions as you can see below for example.
Without those extra state and transitions it is not a DFA if the alphabet is { a , b } .
To avoid those redundant states and transitions and to make modeling easier
we use finite automata called
nondeterministic
finite automata (abbreviated as NFA) .
Below we are going to formally define nondeterministic finite automata (abbreviated as NFS)
and see some examples. As we are going to see later, for any NFA there is a DFA
which accepts the same language and vice versa.
NFAs are quite similar to DFAs. The only difference is in the transition function.
NFAs do not necessarily go to a unique next state. An NFA may not go to any state
from the current state on reading an input symbol or it may select one of several states
nondeterministically (e.g. by throwing a die) as its next state.
Definition of nondeterministic finite automaton
Let Q be a finite set and let 
be a finite set
of symbols.
Also let 
be a function
from Q 
to 2Q , let q0 be a state in Q and
let A be a subset of Q.
We call the elements of Q a state,
the transition function,
q0 the initial state
and A the set of accepting states.
Then a nondeterministic finite automaton is a 5-tuple
< Q , ,
q0 , , A >
Notes on the definition
- As in the case of DFA the set Q in the above definition is simply a set
with a finite number of elements. Its elements can
be interpreted as a state that the system (automaton) is in.
- The transition function is also called a next state
function .
Unlike DFAs an NFA moves into one of the
states given by (q, a) if it receives the input symbol a
while in state q. Which one of the states in
(q, a) to select is determined nondeterministically.
- Note that is a function. Thus for each state q of Q
and for each
symbol a of
(q, a) must be specified. But it can be the empty set,
in which case the NFA aborts its operation.
- As in the case of DFA the accepting states are used to distinguish sequences of
inputs given to the finite automaton.
If the finite automaton is in an accepting state when the input ends i.e. ceases to come,
the sequence of
input symbols given to the finite automaton is "accepted". Otherwise it is not accepted.
- Note that any DFA is also a NFA.
Examples of NFA
Example 1: Q = { 0, 1 }, = { a }, A = { 1 },
the initial state is 0 and is as shown in the following
table.
| State (q) | Input (a) | Next State
(
(q, a) ) |
0 | a | { 1 } |
1 | a | |
A state transition diagram for this finite automaton is given below.
If the alphabet is changed to { a, b }
in stead of
{ a }, this is still an NFA that accepts { a } .
Example 2: Q = { 0, 1, 2 }, = { a, b },
A = { 2 },
the initial state is 0 and is as shown in the following
table.
| State (q) | Input (a) | Next State
(
(q, a) ) |
0 | a | { 1 , 2 } |
0 | b |
|
1 | a | |
1 | b | { 2 } |
2 | a |
|
2 | b | |
Note that for each state there are two rows in the table for
corresponding to the symbols a and b, while in the Example 1 there is only one row
for each state.
A state transition diagram for this finite automaton is given below.
Operation of NFA
Let us see how an automaton operates when some inputs are applied to it.
As an example let us consider the automaton of Example 2 above.
Initially it is in state 0. When it reads the symbol a,
it moves to either state 1 or state 2. Since the state 2 is the accepting state,
if it moves to state 2 and no more inputs are given, then it stays in the accepting state.
We say that this automaton
accepts the string a. If on the other hand it moves to state 1 after reading a,
if the next input is b and if no more inputs are given, then it goes to state 2 and
remains there. Thus the string ab is also accepted by this NFA.
If any other strings are given to this NFA, it does not accept any of them.
Let us now define the function * and
then formalize the concepts of acceptance of strings and languages by NFA.
Test Your Understanding of Definition of NFA
Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
There are two sets of questions.
The following notations are used in the questions:
: \delta
Next -- Language Accepted by NFA
Back to Study Schedule
Back to Table of Contents