Review of * and Other Relevant Materials



Definition of * of NFA

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:

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.

For more click here.

Conversion of NFA- to NFA

Let M1 = < Q1 , , q1,0 , 1 , A1 > be an NFA- that recognizes a language L. Then the NFA M2 = < Q2, , q2,0 , 2 , A2 > that satisfies the following conditions recognizes L:

Q2 = Q1,
q2,0 = q1,0,
2( q, a ) = 1*( q , a ) = ( )

A2 = A1 { q1,0 } if ( { q1,0 } ) A1

      Thus to obtain an NFA M2 = < Q2, , q2,0 , 2 , A2 > which accepts the same language as the given NFA- M1 = < Q1 , , q1,0 , 1 , A1 > does,

first copy the states of Q1 into Q2.
Then for each state q of Q2 and each symbol a of find 2( q , a ) as follows:

Find ( {q} ), that is all the states that can be reached from q by traversing arcs. Then collect all the states that can be reached from each state of ( {q} ) by traversing one arc labeled with the symbol a. The closure of the set of those states is 2( q , a ) .
The set of accepting states A2 is the same as A1 if no accepting states can be reached from the initial state q1,0 through arcs in M1 . Otherwise, that is if an accepting state can be reached from the initial state q1,0 through arcs in M1 , then all the accepting states of M1 plus state q1,0 are the accepting states of M2 .

For more click here.


Definition of * of NFA-

Let < Q , , q0 , , A > be an NFA-.
* is defined recursivelyas follows.

Basis Clause: For any state q of Q,

*( q , ) = ( { q } ) .

Inductive Clause: For any state q, a string y over 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 ) .

For more click here.



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.

-closure for a state is the set of states reachable from the state without reading any symbol.

For more click here.