## 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