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