Finite Automata
Language Accepted by NFA
Subjects to be Learned
- * for NFA
- Language accepted by NFA
- Properties of *
Contents
Here we are going to formally define what is meant by an NFA (nondeterministic finite
automaton)
accepting a string or a language.
We start with the concept of * .
Definition of *
For a state q and string w, *( q , w )
is the set of states that the NFA can reach when it reads the string w
starting at the state q. In general an NFA nondeterministically goes through
a number of states from the state q as it reads the symbols in the string w.
Thus for an NFA < Q , ,
q0 , , A > ,
the function
* :
Q
* -> 2Q
is defined recursively as follows:
Definition of *:
Basis Clause: For any state q of Q, *(
q ,
) = { q }, where
denotes
the empty string.
Inducitve Clause: For any state q of Q, any string y
* and any symbol a
,
*( q , ya ) =
In the definition, the Basis Clause says that an NFA stays in state q when it reads
an empty string at state q
and the Inductive Clause says that the set of states NFA can reach after reading string ya
starting at state q is the set of states it can reach
by reading symbol a after reading string y starting at state q.
Example
For example consider the NFA with the following transition table:
State (q) | Input (a) | Next State
(
(q, a) ) |
0 | a | { 0 , 1 , 3 } |
0 | b | { 2 } |
1 | a | |
1 | b | { 3 } |
2 | a | { 3 } |
2 | b | |
3 | a | |
3 | b | { 1 } |
The transition diagram for this NFA is as given below.
Suppose that the state 3 is an accepting state of this NFA.
Then *( 0 , ab ) can be calculated as follows:
*( 0 , ab )
is the union of
( p, b ) for all p
*( 0 , a ) by the Inductive Clause
of the definition of
* .
Now *( 0 , a ) is the union of
( p, a ) for all p
*( 0 , )
again by the Inductive Clause of the definition of
* .
By the Basis Clause of the definition of *,
*( 0 ,
) = { 0 } .
Hence *( 0 , a ) =
( 0 , a ) = { 0 , 1 , 3 } .
Hence *( 0 , ab )
= ( 0 , b )
( 1 , b )
( 3 , b )
= { 2 }
{ 3 }
{ 1 } = { 1 , 2 , 3 } .
We say that a string x
* is accepted by an NFA < Q, ,
q0, , A >
if and only if *( q0 , x )
A is not empty, that is, if and only if it can reach
an accepting state by reading x starting at the initial state.
The language accepted by an NFA < Q,
,
q0, , A > is the set of strings
that are accepted by the NFA.
Some of the strings accepted by the NFA given above are
, a, ab, aaa, abbbb etc.
and the language it accepts is
a*( ab + a + ba )(bb)* .
* for NFA has properties similar to that for DFA.
Theorem 1: For any state q of Q and any symbol a of
for an NFA   < Q , ,
q0 , , A > ,
*( q , a ) =
( q , a )
Theorem 2: For any state q of Q and any strings x and y over
for an NFA   < Q , ,
q0 , , A > ,
*( q , xy ) =
These theorems can be proven in a manner similar to those for Theorems 1 and 2 for DFA.
Test Your Understanding of * of NFA and its Properties
Indicate which of the following statements are correct and which are not.
Click Yes or No , then Submit.
For the following NFA answer the questions given below.
The following notations are used in the questions:
: \delta
* : \delta^*
: \Lambda
Next -- Definition of NFA with Transitions
Back to Study Schedule
Back to Table of Contents