   DESKTOP

# Algorithms for Compiler Design: THE NFA WITH ∈-MOVES TO THE DFA

7/24/2010 7:59:17 PM
##### 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 δ 0 1 ∈ q0 {q0} φ {q1} q1 φ {q1} {q2} q2 φ {q2} φ A DFA equivalent to this will be: where δ1 0 1 {q0, q1, q2} {q0, q1, q2} {q1, q2} {q1, q2} φ {q1, q2} φ φ φ If we identify the subsets {q0, q1, q2}, {q0, q1, q2} and φ as A, B, and C, respectively, then the automata will be: where δ1 0 1 A A B B C B C C C EXAMPLE 1 Obtain a DFA equivalent to the NFA shown in Figure 1. Figure 1: Example 1 NFA. A DFA equivalent to NFA in Figure 1 will be: � 0 1 {q0} {q0, q1} {q0} {q0, q1} {q0, q1} {q0, q2} {q0, q2} {q0, q1} {q0, q3} {q0, q2, q3}* {q0, q1, q3} {q0, q3} {q0, q1, q3}* {q0, q3} {q0, q2, q3} {q0, q3}* {q0, q1, q3} {q0, q3} 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: {q0} A {q0, q1} B {q0, q2} C {q0, q2, q3} D {q0, q1, q3} E {q0, q3} F then the transition table will be: � 0 1 A B A B B C C B F D* E F E* F D F* E F EXAMPLE 2 Obtain a DFA equivalent to the NFA illustrated in Figure 2. Figure 2: Example 2 DFA equivalent to an NFA. A DFA equivalent to the NFA shown in Figure 2 will be: � 0 1 {q0} {q0} {q0, q1} {q0, q1} {q0, q2} {q0, q1} {q0, q2} {q0} {q0, q1, q3} {q0, q1, q3}* {q0, q2, q3} {q0, q1, q3} {q0, q2, q3}* {q0, q3} {q0, q1, q3} {q0, q3}* {q0, q3} {q0, q1, q3} 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: {q0} A {q0, q1} B {q0, q2} C {q0, q2, q3} D {q0, q1, q3} E {q0, q3} F then the transition table will be: � 0 1 A A B B C B C A E D* F E E* D E F* F E var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>"); Other

 Top 10 REVIEW - First look: Apple Watch

- 3 Tips for Maintaining Your Cell Phone Battery (part 1)

- 3 Tips for Maintaining Your Cell Phone Battery (part 2)     