1CMSC330Finite Automata 2Last Lecture• Finite automata– Alphabet, states…– (, Q, q0, F, )• Types– Deterministic (DFA)– Non-deterministic (NFA)• Reducing RE to NFA– Concatenation– Union– Closureabaabaab aThis Lecture• Reducing NFA to DFA*– ε-closure– Subset algorithm• Minimizing DFA*– Hopcroft reduction• Complementing DFA• Implementing DFA*How NFA Works• When NFA processes a string– NFA may be in several possible states• Multiple transitions with same label• -transitions• Example– After processing “a”• NFA may be in states S1S2S3aS1 S2aS3Reducing NFA to DFA• NFA may be reduced to DFA– By explicitly tracking the set of NFA states• Intuition– Build DFA where • Each DFA state represents a set of NFA states• ExampleS1aS1, S2, S3aS1 S2aNFA DFAS3Reducing NFA to DFA (cont.)• Reduction applied using the subsetalgorithm– DFA state is a subset of set of all NFA states• Algorithm– Input – Output δ– Using 2 -transitions and -closure• We say p q– If it is possible to go from state p to state q by taking only -transitions !∃ "#$ ∈ %&%& '"(∈ '"#(∈ $ '(∈ • -closure(p)– Set of states reachable from p using -transitions alone• Set of states such that • -closure(p) = ') (– Note • -closure(p) always includes p• -closure( ) may be applied to set of states (take union) -closure: Example 1 • Following NFA contains– S1 S2– S2 S3– S1 S3• -closures– -closure(S1) =– -closure(S2) =– -closure(S3) =– -closure( { S1, S2 } ) =S1 S2 S3 { S1, S2, S3 }{ S2, S3 }{ S3 }a{ S1, S2, S3 } ∪ { S2, S3 } -closure: Example 2 • Following NFA contains– S1 S3– S3 S2– S1 S2• -closures– -closure(S1) =– -closure(S2) =– -closure(S3) =– -closure( { S2,S3 } ) =bS1 S2 S3a { S1, S2, S3 }{ S2 }{ S2, S3 }{ S2 } ∪ { S2, S3 } -closure: Practice• Find -closures for following NFA• Find -closures for the NFA you construct for– The regular expression )"*"""*)"Calculating – Set of states reachable from p using exactly one transition on a• Set of states q such that '(∈ = ')'(∈ (– Note may be empty Ø• If no transition from p with label a : Example 1 • Following NFA +',(• Move– move(S1, a) = – move(S1, b) = – move(S2, a) = – move(S2, b) =– move(S3, a) =– move(S3, b) =bS1 S2 S3a{ S2, S3 }{ S3 }aØØØØ3 : Example 2 • Following NFA +',(• Move– move(S1, a) = – move(S1, b) = – move(S2, a) = – move(S2, b) =– move(S3, a) =– move(S3, b) =aS1 S2 S3a{ S2 }b{ S3 }{ S3 }ØØØNFA → DFA Reduction Algorithm• Input ,Output δ• Algorithm– Let = ε-closure(), add it to R // DFA start state– While ∃ an unmarked state ∈ // process DFA state r• Mark r // each state visited once• For each a ∈ Σ // for each letter a– Let S = {s | q ∈ r & move(q,a) = s} // states reached via a– Let e = ε-closure(S) // states reached via ε– If e ∉ R // if state e is newLet R = e ∪ R // add e to R (unmarked)– Let δ = δ ∪ {r, a, e} // add transition re– Let Fd= {r | ∃ s ∈ r with s ∈ Fn} // final if include state in FnNFA → DFA Example 1– Start = ε-closure(-") = ''-"-.(( +''-"-.(( ∈+'-"-.( / '-"-.((+'-#( +ε'-#(+'-#( +∪ '-#(+''-"-.('-#(( δ +δ ∪ ''-"-.('-#(( / '-"-.(,(+0bS1 S2 S3aa{2}{1,3}NFADFANFA → DFA Example 1 (cont.) +''-"-.('-#(( ∈+'-#( / '-#((+0 / '-#(,(+'-.( +ε'-.(+'-.( +∪ '-.(+''-"-.('-#('-.(( δ +δ ∪ ''-#(,'-.((bS1 S2 S3aa b{3}{2}{1,3}NFADFANFA → DFA Example 1 (cont.) +''-"-.('-#('-.(( ∈+'-.( / '-.((+0 / '-.(,(+0 +''-"-.('-.((• Since -.∈ – Done!bS1 S2 S3aa b{3}{2}{1,3}NFADFAR = { {A}, }{C,D}{B,D},NFA → DFA Example 2• NFA{A}{B,D}ab{C,D}• DFA4{E}{C,D},{B,D,E},R = { {A,E}, }NFA → DFA Example 3• NFA • DFA{A,E}{B,D,E}a{C,D}bb {E}abaEquivalence of DFAs and NFAs• Any string from '( to either '( or '1(– Represents a path from to in the original NFANFADFAEquivalence of DFAs and NFAs(cont.)• Can reduce any NFA to a DFA using subset algorithm• How many states in the DFA?– Each DFA state is a subset of the set of NFA states– Given NFA with n states, DFA may have 2nstates• Since a set with n items may have 2nsubsets– Corollary• Reducing a NFA with n states may be O(2n)Minimizing DFA• Result from CS theory– Every regular language is recognizable by a minimum-state DFA that is unique up to state names• In other words– For every DFA, there is a unique DFA with minimum number of states that accepts the same language– Two minimum-state DFAshave same underlying shapebS1 S2 S3abS1 S2S3ccaMinimizing DFA: HopcroftReduction• Intuition– Look for states that can be distinguish from each other• End up in different accept / non-accept state with identical input• Algorithm– Construct initial partition• Accepting & non-accepting states– Iteratively refine partitions (until partitions remain fixed)• Split a partition if members in partition
View Full Document
Unlocking...