Flat_2.3_NFA to DFA b.tech cse notes .pptx

Flat_2.3_NFA to DFA b.tech cse notes .pptx

1. Conversion of an NFA into a DFA

2. Conversion of an NFA into a DFA It is hard for a computer program to simulate an NFA because the transition function is multivalued. The algorithm that called the subset construction will convert an NFA for any language into a DFA that recognizes the same languages.

3. 3 NFA to DFA by subset construction Let N = {Q N ,∑,δ N ,q ,F N } Goal: Build D={ Q D ,∑,δ D ,{q },F D } s.t. L(D)=L(N) Construction: Q D = all subsets of Q N (i.e., power set) F D =set of subsets S of Q N s.t. S ∩F N ≠ Φ δ D : for each subset S of Q N and for each input symbol a in ∑: δ D (S,a) = U δ N (p,a) p in s

4. 4 NFA to DFA construction: Example L = {w | w ends in 01} q q 1 0,1 q 2 1 NFA: δ N 1 q {q ,q 1 } {q } q 1 Ø {q 2 } *q 2 Ø Ø DFA: δ D 1 Ø Ø Ø [q ] {q ,q 1 } {q } [q 1 ] Ø {q 2 } *[q 2 ] Ø Ø [q ,q 1 ] {q ,q 1 } {q ,q 2 } *[q ,q 2 ] {q ,q 1 } {q } *[q 1 ,q 2 ] Ø {q 2 } *[q ,q 1 ,q 2 ] {q ,q 1 } {q ,q 2 } Determine transitions δ D 1 [q ] [q ,q 1 ] [q ] [q ,q 1 ] [q ,q 1 ] [q ,q 2 ] *[q ,q 2 ] [q ,q 1 ] [q ] [q ] 1 [q ,q 1 ] 1 [q ,q 2 ] 1 Idea: To avoid enumerating all of power set, do “lazy creation of states” 2. Retain only those states reachable from {q } 0. Enumerate all possible subsets

5. 5 Eliminating  -transitions Let E = {Q E ,∑,δ E ,q ,F E } be an  -NFA Goal: To b uild DFA D={ Q D ,∑,δ D ,{q D },F D } s.t. L(D)=L(E) Construction: Q D = all reachable subsets of Q E factoring in  -closures q D = ECLOSE(q ) F D =subsets S in Q D s.t. S ∩F E ≠ Φ δ D : for each subset S of Q E and for each input symbol a  ∑: Let R= U δ E (p,a) // go to destination states δ D (S,a) = U ECLOSE(r) // from there, take a union of all their -closures p in s r in R

6. 6 Example:  -NFA  DFA L = {w | w is empty, or if non-empty will end in 01} start q q 1 0,1 1 q 2 q’  δ E 1  *q’ Ø Ø {q’ ,q } q {q ,q 1 } {q } {q } q 1 Ø {q 2 } {q 1 } *q 2 Ø Ø {q 2 } δ D 1 *{q’ ,q } …

7. 7 Example:  -NFA  DFA L = {w | w is empty, or if non-empty will end in 01} start q q 1 0,1 1 q 2 q’  δ E 1  *q’ Ø Ø {q’ ,q } q {q ,q 1 } {q } {q } q 1 Ø {q 2 } {q 1 } *q 2 Ø Ø {q 2 } δ D 1 *{q’ ,q } {q ,q 1 } {q } {q ,q 1 } {q ,q 1 } {q ,q 2 } {q } {q ,q 1 } {q } *{q ,q 2 } {q ,q 1 } {q } {q’ , q } start {q ,q 1 } {q ,q 2 } 1 q 1 1 1 union ECLOSE