Finite Automata
Language Accepted by NFA-
Subjects to be Learned
- -closure
* for NFA-
- Language accepted by NFA-
- Properties of *
Contents
To formally define *
for NFA- , we start with the concept
of -closure for a state which is
the set of states reachable from the state without reading any symbol.
Using that concept we define *
and then strings and languqges accepted by NFA-.
Definition of -closure
Let < Q , 
,
q0 , , A > be
an NFA- .
Let us denote the -closure of a set S of states of Q
by ( S ). Then ( S )
is defined recursively as follows:
Basis Clause: S 
( S )
Inductive Clause: For any state q of Q, if q 
( S ) , then ( q , )
( S ) .
Extremal Clause: Nothing is in ( S ) unless it is obtained by the above two clauses.
For the NFA- of the above figure,
( { 2 } ) is obtained as follows:
First { 2 }
( { 2 } ) ,
that is, 2
( { 2 } ) .
Then since 2
( { 2 } ) , by the Inductive Clause,
( 2 , )
( { 2 } ) .
Since ( 2 , ) = { 3 , 4 }, we now have { 2 , 3 , 4 }
( { 2 } ) .
Since 3 and 4 have been added to ( { 2 } ) ,
( 3 , ) = { 5 }
and ( 4 , ) =
must be included in
( { 2 } ) .
Thus now { 2 , 3 , 4 , 5 }
( { 2 } ) .
Though 5 has become a memeber of the closure,
since ( 5 ,
) is empty, no new members are added to
( { 2 } ) .
Since ( q ,
) has been examined for all the states currently in
( { 2 } ) and no more elements are added to it,
this process of generating the closure terminates
and
( { 2 } ) = { 2 , 3 , 4 , 5 } is obtained.
As we can see from the example, ( S )
is the set of states that can be reached from the states of S by traversing
any number of arcs. That is, it is the set of states
that can be reached from the states of S without reading any symbols
in .
Now with this -closure, we can define
* recursively as follows:
As in the cases of DFA and NFA, *
gives the result of applying the transition function
repeatedly as dictated by the given string.
Definition of *
* is going to be defined recursively.
Let < Q , ,
q0 , , A > be an
NFA-.
Basis Clause: For any state q of Q,
*( q ,
) = ( { q } ) .
Inductive Clause: For any state q, a string y in * and a symbol a in ,
*( q , ya ) =
( 
) .
What the Inductive Clause means is that
*( q , ya ) is obtained by first
finding the states that can be reached from q by reading y
( *( q , y ) ), then
from each of those states p by reading a
(i.e. by finding ( p , a ) ), and then by reading
's
( i.e. by taking the
closure of the
( p , a )'s ) .
Example : For the NFA- of the following figure, *( 0 , ab ) can be
obtained as below:
First let us compute
*( 0 , a ) .
For that we need ( { 0 } ).
Since it is the set of states reached by traversing the arcs from state 0, ( { 0 } ) = { 0 , 3 , 4 } .
Next from each of the states in ( { 0 } ) we read symbol
a and move to another state
(i.e. apply ). They are
( 0 , a ) = { 1 } ,
( 3 , a ) =
( 4 , a ) = { 5 }.
Hence = { 1 , 5 } for q = 0 .
We then traverse the arcs from
{ 1 , 5 } to get to the states in
*( 0 , a ) .
Since
( { 1 } ) = { 1 , 2 , 3 } and
( { 5 } ) = { 5 } ,
*( 0 , a ) = { 1 , 2 , 3 , 5 } .
Then to find *( 0 , ab )
read b from each of the states in *( 0 , a ) and then take the
arcs from there.
Now ( 1 , b ) , ( 3 , b ) and ( 5 , b ) are empty sets, and
( 2 , b ) = { 4 } .
Thus
Since ( { 4 } ) = { 3 , 4 } ,
*( 0 , ab ) = { 3 , 4 } .
A string x is accepted by an NFA-
< Q , ,
q0 , , A >
if and only if *( q0 , x ) contains at least one accepting state.
The language
accepted by an NFA-
< Q , ,
q0 , , A >
is the set of strings accepted by the NFA- .
For example the NFA- of the figure given above accepts the language { , a ,
ab } .
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 -- Equivalence of FAs
Back to Study Schedule
Back to Table of Contents