2.6 MINIMIZATIONOPTIMIZATION OF A DFA

2.5 THE NFA WITH ˆˆ -MOVES TO THE DFA

There always exists a DFA equivalent to an NFA with ˆˆ -moves which can be obtained as follows :

A DFA equivalent to this NFA will be:

If this transition generates a new subset of Q , then it will be added to Q ₁ ; and next time transitions from it are found, we continue in this way until we cannot add any new states to Q ₁ . After this, we identify those states of the DFA whose subset representations contain at least one member of F . If ˆˆ -closure( q ) does not contain a member of F , and the set of such states of DFA constitute F ₁ , but if ˆˆ -closure( q ) contains a member of F , then we identify those members of Q ₁ whose subset representations contain at least one member of F , or q and F ₁ will be set as a member of these states.

Consider the following NFA with ˆˆ -moves:

where

		1	ˆˆ
q	{ q }		{ q 1 }
q 1		{ q 1 }	{ q 2 }
q 2		{ q 2 }

A DFA equivalent to this will be:

where

1		1
{ q , q 1 , q 2 }	{ q , q 1 , q 2 }	{ q 1 , q 2 }
{ q 1 , q 2 }		{ q 1 , q 2 }

If we identify the subsets { q , q ₁ , q ₂ }, { q , q ₁ , q ₂ } and as A , B , and C , respectively, then the automata will be:

where

1		1
A	A	B
B	C	B
C	C	C

EXAMPLE 2.1

Obtain a DFA equivalent to the NFA shown in Figure 2.7.

Figure 2.7: Example 2.1 NFA.

 

A DFA equivalent to NFA in Figure 2.7 will be:

		1
{ q }	{ q , q 1 }	{ q }
{ q , q 1 }	{ q , q 1 }	{ q , q 2 }
{ q , q 2 }	{ q , q 1 }	{ q , q 3 }
{ q , q 2 , q 3 }*	{ q , q 1 , q 3 }	{ q , q 3 }
{ q , q 1 , q 3 }*	{ q , q 3 }	{ q , q 2 , q 3 }
{ q , q 3 }*	{ q , q 1 , q 3 }	{ q , q 3 }

where { q } corresponds to the initial state of the automata, and the states marked as * are final states. lf we rename the states as follows:

{ q }	A
{ q , q 1 }	B
{ q , q 2 }	C
{ q , q 2 , q 3 }	D
{ q , q 1 , q 3 }	E
{ q , q 3 }	F

then the transition table will be:

		1
A	B	A
B	B	C
C	B	F
D *	E	F
E *	F	D
F *	E	F

EXAMPLE 2.2

Obtain a DFA equivalent to the NFA illustrated in Figure 2.8.

Figure 2.8: Example 2.2 DFA equivalent to an NFA.

 

A DFA equivalent to the NFA shown in Figure 2.8 will be:

		1
{ q }	{ q }	{ q , q 1 }
{ q , q 1 }	{ q , q 2 }	{ q , q 1 }
{ q , q 2 }	{ q }	{ q , q 1 , q 3 }
{ q , q 1 , q 3 }*	{ q , q 2 , q 3 }	{ q , q 1 , q 3 }
{ q , q 2 , q 3 }*	{ q , q 3 }	{ q , q 1 , q 3 }
{ q , q 3 }*	{ q , q 3 }	{ q , q 1 , q 3 }

where { q } corresponds to the initial state of the automata, and the states marked as * are final states. If we rename the states as follows:

{ q }	A
{ q , q 1 }	B
{ q , q 2 }	C
{ q , q 2 , q 3 }	D
{ q , q 1 , q 3 }	E
{ q , q 3 }	F

then the transition table will be:

		1
A	A	B
B	C	B
C	A	E
D *	F	E
E *	D	E
F *	F	E