Lecture Notes 10 State Minimization 1 State Minimization for DFAs Read K & S 2.7 Do Homework 10. State Minimization Consider: a a b b 1 2 3 4 a a b b b 5 a b a 6 Is this a minimal machine? State Minimization Step (1): Get rid of unreachable states. a 1 2 b a, b 3 State 3 is unreachable. Step (2): Get rid of redundant states. b a 1 2 a b b 3 a States 2 and 3 are redundant. Getting Rid of Unreachable States We can't easily find the unreachable states directly. But we can find the reachable ones and determine the unreachable ones from there. An algorithm for finding the reachable states: a 1 2 b a, b 3Lecture Notes 10 State Minimization 2 Getting Rid of Redundant States Intuitively, two states are equivalent to each other (and thus one is redundant) if all strings in Σ* have the same fate, regardless of which of the two states the machine is in. But how can we tell this? The simple case: a, b 1 2 b a 3 a, b Two states have identical sets of transitions out. Getting Rid of Redundant States The harder case: b a 1 2 a b b 3 a The outcomes are the same, even though the states aren't. Finding an Algorithm for Minimization Capture the notion of equivalence classes of strings with respect to a language. Capture the (weaker) notion of equivalence classes of strings with respect to a language and a particular FSA. Prove that we can always find a deterministic FSA with a number of states equal to the number of equivalence classes of strings. Describe an algorithm for finding that deterministic FSA. Defining Equivalence for Strings We want to capture the notion that two strings are equivalent with respect to a language L if, no matter what is tacked on to them on the right, either they will both be in L or neither will. Why is this the right notion? Because it corresponds naturally to what the states of a recognizing FSM have to remember. Example: (1) a b b a b (2) b a b a b Suppose L = {w ∈ {a,b}* : |w| is even}. Are (1) and (2) equivalent? Suppose L = {w ∈ {a,b}* : every a is immediately followed by b}. Are (1) and (2) equivalent?Lecture Notes 10 State Minimization 3 Defining Equivalence for Strings If two strings are equivalent with respect to L, we write x ≈L y. Formally, x ≈L y if, ∀z ∈ Σ*, xz ∈ L iff yz ∈ L. Notice that ≈L is an equivalence relation. Example: Σ = {a, b} L = {w ∈ Σ* : every a is immediately followed by b } ε a b aa bb aba aab bbb baa The equivalence classes of ≈L: |≈L | is the number of equivalence classes of ≈L. Another Example of ≈≈≈≈L Σ = {a, b} L = {w ∈ Σ* : |w| is even} ε a b aa bb aba aab bbb baa aabb bbaa aabaa The equivalence classes of ≈L: Yet Another Example of ≈≈≈≈L Σ = {a, b} L = aab*a ε a b aa ab ba bb aaa aba aab bab aabb aabaa aabbba aabbaa The equivalence classes of ≈L: An Example of ≈≈≈≈L Where All Elements of L Are Not in the Same Equivalence Class Σ = {a, b} L = {w ∈ {a, b}* : no two adjacent characters are the same} ε a b aa bb aba aab baa aabb aabaa aabbba aabbaa The equivalence classes of ≈L:Lecture Notes 10 State Minimization 4 Is |≈≈≈≈L| Always Finite? Σ = {a, b} L = anbn ε a b aa aba aaa aaaa aaaaa The equivalence classes of ≈L: Bringing FSMs into the Picture ≈L is an ideal relation. What if we now consider what happens to strings when they are being processed by a real FSM? Σ = {a, b} L = {w ∈ Σ* : |w| is even} a 1 2 a, b b a, b 3 Define ~M to relate pairs of strings that drive M from s to the same state. Formally, if M is a deterministic FSM, then x ~M y if there is some state q in M such that (s, x) |-*M (q, ε) and (s, y) |-*M (q, ε). Notice that M is an equivalence relation. An Example of ~M Σ = {a, b} L = {w ∈ Σ* : |w| is even} a 1 2 a, b b a, b 3 ε a b aa bb aba aab bbb baa aabb bbaa aabaa The equivalence classes of ~M: |~M| =Lecture Notes 10 State Minimization 5 Another Example of ~M Σ = {a, b} L = {w ∈ Σ* : |w| is even} a,b 1 2 a, b ε a b aa bb aba aab bbb baa aabb bbaa aabaa The equivalence classes of ~M: |~M| = The Relationship Between ≈≈≈≈L and ~M ≈L: [ε, aa, bb, aabb, bbaa] |w| is even [a, b, aba, aab, bbb, baa, aabaa] |w| is odd ~M, 3 state machine: q1: [ε, aa, bb, aabb, bbaa] |w| is even q2: [a, aba, baa, aabaa] (ab ∪ ba ∪ aa ∪ bb)*a q3: [b, aab, bbb] (ab ∪ ba ∪ aa ∪ bb)*b ~M, 2 state machine: q1: [ε, aa, bb, aabb,
View Full Document
Unlocking...