Homework 10 State Minimization 1 CS 341 Homework 10 State Minimization 1. (a) Give the equivalence classes under ≈L for these languages: (i) L = (aab ∪ ab)* (ii) L = {x : x contains an occurrence of aababa} (iii) L = {xxR : x ∈ {a, b}*} (iv) L = {xx : x ∈ {a, b}*} (v) Ln = {a, b}a{a, b}n, where n > 0 is a fixed integer (vi) The language of balanced parentheses (b) For those languages in (a) for which the answer is finite, give a deterministic finite automaton with the smallest number of states that accepts the corresponding language. 2. Let L = {x ∈ {a, b}* : x contains at least one a and ends in at least two b's}. (a) Write a regular expression for L. (b) Construct a deterministic FSM that accepts L. (c) Let RL be the equivalence relation of the Myhill-Nerode Theorem. What partition does RL induce on the set {a, bb, bab, abb, bba, aab, abba, bbaa, baaba}? (d) How many equivalence classes are there in the partition induced on Σ* by RL? 3. Let L = {x ∈ {a, b}* : x begins with a and ends with b}. (a) What is the nature of the partition induced on Σ* by RL, the equivalence relation of the Myhill-Nerode Theorem? That is, how many classes are there in the partition and give a description of the strings in each. (b) Using these equivalence classes, construct the minimum state deterministic FSM that accepts L. 4. Suppose that we are given a language L and a deterministic FSM M that accepts L. Assume L is a subset of {a, b, c}*. Let RL and RM be the equivalence relations defined in the proof of the Myhill-Nerode Theorem. True or False: (a) If we know that x and y are two strings in the same equivalence class of RL, we can be sure that they are in the same equivalence class of RM. (b) If we know that x and y are two strings in the same equivalence class of RM, we can be sure that they are in the same equivalence class of RL. (c) There must be at least one equivalence class of RL that has contains an infinite number of strings. (d) RM induces a partition on {a, b, c}* that has a finite number of classes. (e) If ε ∈ L, then [ε] (the equivalence class containing ε) of RL cannot be an infinite set. 5. Use the Myhill-Nerode Theorem to prove that {anbmcmax(m,n)bpdp : m, n, p ≥ 0} is not regular. 6. (a) In class we argued that the intersection of two regular languages was regular on the basis of closure properties of regular languages. We did not show a construction for the FSM that recognizes the intersection of two regular languages. Such a construction does exist, however, and it is suggested by the fact that L1 ∩ L2 = Σ* - ((Σ* - L1) ∪ (Σ* - L2)). Given two deterministic FSMs, M1 and M2, that recognize two regular languages L1 and L2, we can construct an FSM that recognizes L = L1 ∩ L2 (in other words strings that have all the required properties of both L1 and L2), as follows: 1. Construct machines M1' and M2', as deterministic versions of M1 and M2. This step is necessary because complementation only works on deterministic machines. 2. Construct machines M1'' and M2'', from M1' and M2', using the construction for complementation, that recognize Σ* - L1 and Σ* - L2, respectively. 3. Construct M3, using the construction for union and the machines M1'' and M2'', that recognizes ((Σ* - L1) ∪ (Σ* - L2)). This will be a nondeterministic FSM. 4. Construct M4, the deterministic equivalent of M3. 5. Construct ML, using the construction for complementation, that recognizes Σ* - ((Σ* - L1) ∪ (Σ* - L2)). Now consider: Σ = {a, b} L1 = {w ∈ Σ* : all a's occur in pairs} e.g., aa, aaaa, aabaa, aabbaabbb ∈ L1 aaa, baaab, ab ∉ L1Homework 10 State Minimization 2 L2 = {w ∈ Σ* : w contains the string bbb} Use the procedure outlined above to construct an FSM ML that recognizes L = L1 ∩ L2. Is ML guaranteed to be deterministic? (b) What are the equivalence classes under ≈L for the language L = L1 ∩ L2? (c) What are the equivalence classes under ~M for ML in (a) above? (d) Show how ~M is a refinement of ≈L . (e) Use the minimization algorithm that we have discussed to construct from ML in (a) above a minimal state machine that accepts L. 7. If you had trouble with this last one, make up another pair of L1 and L2 and try again. Solutions 1. (a) (i) L = (aab ∪ ab)* 1. [ε, aab, ab, and all other elements of L] 2. [a or wa : w ∈ L] 3. [aa or waa : w ∈ L] 4. [everything else, i.e., strings that can never become elements of L because they contain illegal substrings such as bb or aaa] (ii) L = {x : s contains an occurrence of aababa} 1. [(a ∪ b)*aababa(a ∪ b)*, i.e., all elements of L] 2. [ε or any string not in L and ending in b but not in aab or aabab, i.e., no progress yet on "aababa"] 3. [wa for any w ∈ [2]; alternatively, any string not in L and ending in a but not in aa, aaba, or aababa] 4. [any string not in L and ending in aa] 5. [any string not in L and ending in aab] 6. [any string not in L and ending in aaba] 7. [any string not in L and ending in aabab] Note that this time there is no "everything else". Strings never become hopeless in this language. They simply fail if we get to the end without finding "aababa". (iii)L = {xxR : x ∈ {a, b}*} 1. [a, which is the only string for which the continuations that lead to acceptance are all strings of the form wa : where w ∈ L] 2. [b, which is the only string for which the continuations that lead to acceptance are all strings of the form wb : where w ∈ L] 3. [ab, which is the only string for which the continuations that lead to acceptance are all strings of the form wba : where w ∈ L] 4. [aa, which is the only string for which the continuations that lead to acceptance are all strings of the form waa : where w ∈ L] And so forth. Every string is in a distinct equivalence class. (iv) L = {xx : x ∈ {a, b}*} 1. [a, which is the only string for which the continuations that lead to acceptance are all strings that would be in L except that they are missing a leading a] 2. [b, which is the only string for which the continuations that lead to acceptance are all strings that would be in L except that they are missing a leading b] 3. [ab, which is the …
View Full Document
Unlocking...