Finite Automata

Language Accepted by NFA

Subjects to be Learned

^* for NFA
Language accepted by NFA
Properties of ^*

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 ,

, q₀ ,

, A > , the function

^* : Q ^* -> 2^Q
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,

, q₀,

, A > if and only if

^*( q₀ , 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,

, q₀,

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

, q₀ ,

, A > ,

^*( q , a ) =

( q , a )

Theorem 2: For any state q of Q and any strings x and y over

for an NFA < Q ,

, q₀ ,

, 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

Finite Automata

Language Accepted by NFA

Subjects to be Learned

Contents

Test Your Understanding of * of NFA and its Properties

Test Your Understanding of ^* of NFA and its Properties