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 Q1; and next time transitions from it are found, we continue in this way until we cannot add any new states to Q1. After this, we identify those states of the DFA whose subset representations contain at least one member of F. If ∈-closure(q0) does not contain a member of F, and the set of such states of DFA constitute F1, but if ∈-closure(q0) contains a member of F, then we identify those members of Q1 whose subset representations contain at least one member of F, or q0 and F1 will be set as a member of these states.
Consider the following NFA with ∈-moves:
where
A DFA equivalent to this will be:
where
If we identify the subsets {q0, q1, q2}, {q0, q1, q2} and φ as A, B, and C, respectively, then the automata will be:
where
EXAMPLE 1
Obtain a DFA equivalent to the NFA shown in Figure 1.
A DFA equivalent to NFA in Figure 1 will be:
where {q0} corresponds to the initial state of the automata, and the states marked as * are final states. lf we rename the states as follows:
then the transition table will be:
EXAMPLE 2
Obtain a DFA equivalent to the NFA illustrated in Figure 2.
A DFA equivalent to the NFA shown in Figure 2 will be:
where {q0} corresponds to the initial state of the automata, and the states marked as * are final states. If we rename the states as follows:
then the transition table will be:
|
