Problem 1.2: A string z E {0,1}* is said to be balanced if it has exactly the same number of O's and ls. Let L be the language consisting of all strings x E {0, 1}* that contain at least one balanced substring with length at least 6. [Note: the definition would be far less interesting if 6 is changed to 2 :-).] For example, 11011011101 & L but 11101100110 L (because of the bold substring). Given a long string x of length n, deciding whether x E L may at first seem to require a lot of effort, as there are O(na) substrings to check. But it turns out we only need to check O(n) substrings... More precisely, for xe {0,1}*, prove the following fact: X E L if and only if x contains a balanced substring of length between 6 and 11. (Hint: in the more difficult direction, assuming that x does not contain a balanced substring of length between 6 and 11, prove that every substring z with length at least 6 is unbalanced, by induction on [21.] [More Hint: it may be helpful to first prove the following observation: if x is a balanced string that starts with a 0 and ends with a 0, then we can decompose x as uv for shorter strings u and v where both u and v are balanced. To prove this observation, let #o(i) and #1(i) denote the number of O's and ls in the first i symbols of x, and apply the intermediate value theorem to the function #o(i) #1(i) (over i = 1, ..., |2c| 1)...] Problem 1.2: A string z E {0,1}* is said to be balanced if it has exactly the same number of O's and ls. Let L be the language consisting of all strings x E {0, 1}* that contain at least one balanced substring with length at least 6. [Note: the definition would be far less interesting if 6 is changed to 2 :-).] For example, 11011011101 & L but 11101100110 L (because of the bold substring). Given a long string x of length n, deciding whether x E L may at first seem to require a lot of effort, as there are O(na) substrings to check. But it turns out we only need to check O(n) substrings... More precisely, for xe {0,1}*, prove the following fact: X E L if and only if x contains a balanced substring of length between 6 and 11. (Hint: in the more difficult direction, assuming that x does not contain a balanced substring of length between 6 and 11, prove that every substring z with length at least 6 is unbalanced, by induction on [21.] [More Hint: it may be helpful to first prove the following observation: if x is a balanced string that starts with a 0 and ends with a 0, then we can decompose x as uv for shorter strings u and v where both u and v are balanced. To prove this observation, let #o(i) and #1(i) denote the number of O's and ls in the first i symbols of x, and apply the intermediate value theorem to the function #o(i) #1(i) (over i = 1, ..., |2c| 1)...]
