Homework 3 Languages and Regular Expressions 1 CS 341 Homework 3 Languages and Regular Expressions 1. Describe in English, as briefly as possible, each of the following (in other words, describe the language defined by each regular expression): (a) L( ((a*a) b) ∪ b ) (b) L( (((a*b*)*ab) ∪ ((a*b*)*ba))(b ∪ a)* ) 2. Rewrite each of these regular expressions as a simpler expression representing the same set. (a) ∅* ∪ a* ∪ b* ∪ (a ∪ b)* (b) ((a*b*)* (b*a*)*)* (c) (a*b)* ∪ (b*a)* 3. Let Σ = {a, b}. Write regular expressions for the following sets: (a) All strings in Σ* whose number of a's is divisible by three. (b) All strings in Σ* with no more than three a's. (c) All strings in Σ* with exactly one occurrence of the substring aaa. 4. Which of the following are true? Prove your answer. (a) baa ∈ a*b*a*b* (b) b*a* ∩ a*b* = a* ∪ b* (c) a*b* ∩ c*d* = ∅ (d) abcd ∈ (a(cd)*b)* 5. Show that L((a ∪ b)*) = L(a* (ba*)*). 6. Consider the following: (a) ((a ∪ b) ∪ (ab))* (b) (a+ anbn) (c) ((ab)* ∅) (d) (((ab) ∪ c)* ∩ (b ∪ c*)) (e) (∅* ∪ (bb*)) (i) Which of the above are “pure” regular expressions? (ii) For each of the above that is a regular expression, give a simplified equivalent “pure” regular expression. (iii) Which of the above represent regular languages? 7. True - False: For all languages L1, L2, and L3 (a) (L1L2)* = L1*L2* (b) (L1 ∪ L2)* = L1* ∪ L2* (c) (L1 ∪ L2) L3 = L1 L3 ∪ L2 L3 (d) (L1 L2) ∪ L3 = (L1 ∪ L3) (L2 ∪ L3) (e) L1+)* = L1* (f) (L1+)+ = L1+ (g) (L1*)+ = (L1+)* (h) L1* = L1+ ∪ ∅ (i) (ab)*a = a(ba)* (j) (a ∪ b)* b (a ∪ b)* = a* b (a ∪ b)* (k) [(a ∪ b)* b (a ∪ b)* ∪ (a ∪ b)* a (a ∪ b)*] = (a ∪ b)* (l) [(a ∪ b)* b (a ∪ b)* ∪ (a ∪ b)* a (a ∪ b)*] = (a ∪ b)+ (m) [(a ∪ b)* b a (a ∪ b)* ∪ a*b*] = (a ∪ b)*Homework 3 Languages and Regular Expressions 2 (n) (L1L2L3)* = L1*L2*L3* (o) (L1* ∪ L3*) = (L1* ∪ L3*)* (p) L1* L1 = L1+ (q) (L1 ∪ L2)* = (L2 ∪ L1)* (r) L1* (L2 ∪ L3)+ = (L1* L2+ ∪ L1* L3+) (s) ∅ L1* = ∅ (t) ∅ L1* = {ε} (u) (L1 - L2) = (L2 - L1) (v) ((L1 L2) ∪ (L1 L3))* = (L1 (L2 ∪ L3))* 8. Let L = {w ∈ {a, b}* : w contains bba as a substring}. Find a regular expression for {a, b}* - L. 9. Let Σ = {a,b}. For each of the following sets of strings (i.e., languages) L, first indicate which of the example strings are in the language and which are not. Then, if you can, write a concise description, in English, of the strings that are in the language. Example strings: (1) aaabbb, (2) abab, (3) abba, (4) ε (a) L = {w : for some u ∈ Σ*, w = uRu} (b) L = {w : ww = www} (c) L = {w : for some u ∈ Σ*, www = uu} 10. Write a regular expression for the language consisting of all odd integers without leading zeros. 11. Let Σ = {a, b}. Let L = {ε, a, b}. Let R be a relation defined on Σ* as follows: ∀xy, xRy iff y = xb. Let R′ be the reflexive, transitive closure of L under R. Let L′ = {x : ∃y ∈ L such that yR′x}. Write a regular expression for L′. Solutions 1. (a) Any string of a's and/or b's with zero or more a's followed by a single b. (b) Any string of a's and/or b's with at least one occurrence of ab or ba. 2. (a) ∅* = {ε}, and ε ⊆ (a ∪ b)*. a* ⊆ (a ∪ b)*. b* ⊆ (a ∪ b)*. So since the first three terms describe subsets of the last one, unioning them into the last one doesn't add any elements. Thus we can write simply (a ∪ b)*. (b) To solve this one, we'll use some identities for regular expressions. We don't have time for an extensive study of such identities, but these are useful ones: ((a*b*)* (b*a*)*)* = Using (A*B*)* = (A ∪ B)* (Both simply describe any string that is composed of elements of A and elements of B concatenated together in any order) ((a ∪ b)*(b ∪ a)*)* = Using (A ∪ B) = (B ∪ A) (Set union is commutative) ((a ∪ b)*(a ∪ b)*)* = Using A*A* = A* ((a ∪ b)*)* = Using (A*)* = A* (a ∪ b)*Homework 3 Languages and Regular Expressions 3 (c) (a*b)* ∪ (b*a)* = (a ∪ b)* (In other words, all strings over {a, b}.) How do we know that? (a*b)* is the union of ε and all strings that end in b. (b*a)* is the union of ε and all strings that end in a. Clearly any string over {a, b} must either be empty or it must end in a or b. So we've got them all. 3. (a) The a's must come in groups of three, but of course there can be arbitrary numbers of b's everywhere. So: (b*ab*ab*a)*b* Since the first expression has * around it, it can occur 0 or more times, to give us any number of a's that is divisible by 3. (b) Another way to think of this is that there are three optional a's and all the b's you want. That gives us: b* (a ∪ ε) b* (a ∪ ε) b* (a ∪ ε) b* (c) Another way to think of this is that we need one instance of aaa. All other instances of aa must occur with either b or end of string on both sides. The aaa can occur anywhere so we'll plunk it down, then list the options for everything else twice, once on each side of it: (ab ∪ aab ∪ b)* aaa (ba ∪ baa ∪ b)* 4. (a) True. Consider the defining regular expression: a*b*a*b*. To get baa, take no a's, then one b, then two a's then no b's. (b) True. We can prove that two sets X and Y are equal by showing that any string in X must also be in Y and vice versa. First we show that any string in b*a* ∩ a*b* (which we'll call X) must also be in a* ∪ b* (which we'll call Y). Any string in X must have two properties: (from b*a*): all b's come before all a's; and (from a*b*): all a's come before all b's. The only way to have both of these properties simultaneously is to be composed of only a's or only b's. That's exactly what it takes to be in Y. Next we must show that every string in Y is in X. Every string in Y is either of the form …
View Full Document
Unlocking...