NFA and Kleeneâ€™s Theorem

<< NFA with Null String

NFA corresponding to Concatenation of FAs >>

Theory of Automata

(CS402)

Theory of Automata

Lecture N0. 17

Reading Material

Chapter 7

Introduction to Computer Theory

Summary

converting NFA to FA (method 3), example, NFA and Kleene's theorem method 1, examples, NFA and

Kleene's theorem method 2 , NFA corresponding to union of FAs, example

Method 3: As discussed earlier that in an NFA, there may be more than one transition for a certain letter and

there may not be any transition for certain letter, so starting from the initial state corresponding to the initial

state of given NFA, the transition table along with new labels of states, of the corresponding FA, can be built

introducing an empty state for a letter having no transition at certain state and a state corresponding to the

combination of states, for a letter having more than one transitions. Following are the examples

Example

Consider the following NFA which accepts the language of strings containing bb

a,b

x3+

x1-

Using the method discussed earlier, the transition table corresponding to the required FA may be constructed as

New States after reading

Old States

z1-∫x1

x1∫z1

(x1,x2)∫z2

z2∫(x1,x2)

)∫x1∫z1

(x1 ,x2,x3) ∫z3

(x1 ,

z3+∫(x1,x2,x3)

(x1,x3)∫z4

(x1 ,x2,x3)∫z3

z4+∫ (x1,x3)

(x1,x3)∫z4

(x1 ,x2,x3)∫z3

The corresponding transition diagram follows as

z3+

z1-

z4+

NFA and Kleene's Theorem

It has been discussed that, by Kleene's theorem part III, there exists an FA corresponding to a given RE. If the

given RE is as simple as r = aa+bbb or r = a(a+b)*, the corresponding FAs can easily be constructed. However,

for a complicated RE, the RE can be decomposed into simple REs corresponding to which the FAs can easily be

constructed and hence, using the method, constructing the FAs corresponding to sum, concatenation and closure

of FAs, the required FA can also be constructed. It is to be noted that NFAs also help in proving Kleene's

theorem part III, as well. Two methods are discussed in the following.

NFA and Kleene's Theorem

Method 1:

The method is discussed considering the following example.

Example

To construct the FAs for the languages L1 = {a}, L2 = {b} and L3 = {Y}

Step 1: Build NFA1, NFA2 and NFA3 corresponding to L1, L2 and L3 , respectively as shown in the following

diagram

Theory of Automata

(CS402)

NFA1

NFA2

NFA3

Step 2:

As discussed earlier for every NFA there is an FA equivalent to it, hence there must be FAs for the above

mentioned NFAs as well. The corresponding FAs can be considered as follows

a,b

FA1

FA2

a,b

FA3

NFA and Kleene's Theorem method 2

It may be observed that if an NFA can be built corresponding to union, concatenation and closure of FAs

corresponding to the REs, then converting the NFA, thus, obtained into an equivalent FA, this FA will

correspond to the given RE.

Followings are the procedures showing how to obtain NFAs equivalent to union, concatenation and closure of

FAs

NFA corresponding to Union of FAs

Method

Introduce a new start state and connect it with the states originally connected with the old start state with the

same transitions as the old start state, then remove the ve sign of old start state. This creates non-determinism

and hence results in an NFA.

Example

x1-

NFA1

x4+

a,b

y2+

y1-

NFA2

Theory of Automata

(CS402)

x4+

a, b

y2+

NFA equivalent to FA1«FA2

Table of Contents: