1. Which of the following strings is NOT in the Kleene closure of the language {011,10,110} ? a) 10110011 b) 011011110 c) 01110111 d) 0111010 2. Consider the following identities for regular expressions; some are false and some are true. You are asked to decide which and in case it is false to provide the correct counterexample. (a) R(S+T)=RS+RT (b) (R)=R (c) (RS)=(R+S) (d) (R+S)=R+S (e) S(RS+S)R=RRS(RRS) (f) (RS+R)R=R(SR+R) a) (b) is false and a counterexample is: R={ab},T={a},S={b} b) (a) is false and a counterexample is: R={ab},T={a},S={b} c) (d) is false and a counterexample is: R={a,},T={b},S={a,} d) (d) is false and a counterexample is: R={ab},T={a},S={b} 3. Which among the following languages is not regular (cannot be defined by a regular expression or finite automaton)? a) L={xx=(abmc)n,n,m positive integers } b) L={xx=camcbn,n,m positive integers } c) L={xx=(ab2c)n,n a positive integer\} d) L={xx=(a2b2c2)n,n a positive integer } 4. Find, in the list below, a regular expression whose language is the reversal of the language of this regular expression: 10(2+3). Recall that the reversal of a language is formed by reversing all its strings, and the reversal of a string a1a2an is ana2a1. a) (2+3)10 b) 0(2+3)1 c) (2+3)01 d) 01(2+ 5. The operation DM(L) is defined as follows: 1. Throw away every even-length string from L. 2. For each odd-length string, remove the middle character. For example, if L={001,1100,10101}, then DM(L) ={01,1001}. That is, even-length string 1100 is deleted, the middle character of 001 is removed to make 01, and the middle character of 10101 is removed to make 1001. It turns out that if L is a regular language, DM(L) may or may not be regular. For each of the following languages L, determine what DM(L) is, and tell whether or not it is regular. - L1 : the language of regular expression (01)0. - L2 : the language of regular expression (0+1)1(0+1). - L3 : the language of regular expression (101). - L4 : the language of regular expression 0011. Now, identify the true statement below, a) DM(L2) is regular; it is the language of regular expression (0+1). b) DM(L- L1) is not regular; it consists of all strings of the form (01)n(00) (10)n. c) DM(L- L2) is regular; it is the language of regular expression ((0+1) (0+1)). d) DM(L3) is regular; it is the language of regular expression 10(101101)01. 6. Identify from the list below the regular expression that generates all and only the strings over alphabet {0,1} that end in 1 . a) (0+1)10 b) (00+01+10+11)1 c) 0+(0+1)1 d) (01+)+ 7. Here are seven regular expressions: 1. (0+10) 2. (0+10) 3. (0+10) 4. (0+1)) 5. (0+1) 6. (0+10) 7. (0+1) Determine the language of each of these expressions. Then, find in the list below a pair of equivalent expressions. a) (0+10) and (0+1) b) (0+10) and (0+1) c) (0+10) and (0+10) d) (0+10) and (0+1) 8. The language of regular expression (0+10) is the set of all strings of 0 's and 1 's such that every 1 is immediately followed by a 0 . Describe the complement of this language (with respect to the alphabet {0,1}) and identify in the list below the regular expression whose language is the complement of L((0+10)) a) (0+1)1(+11(0+1)) b) (0+10)(1+11(0+1)) c) (1+01) d) (0+1)(1+11)(0+1) 9. Converting a DFA such as the following: to a regular expression requires us to develop regular expressions for limited sets of paths - those that take the automaton from one particular state to another particular state, without passing through some set of states. For the automaton above, determine the languages for the following limitations: 1. LAA the set of path labels that go from A to A without passing through C or D. 2. LAB= the set of path labels that go from A to B without passing through C or D. 3. LBA= the set of path labels that go from B to A without passing through C or D. 4. LBB= the set of path labels that go from B to B without passing through C or D. Then, identify a correct regular expression from the list below. Note: there are several different regular expressions possible for each of these languages. However, each of the correct answers can be thought of as built from more limited components. For example, the regular expression 1 is the set of path labels that go from A to B without passing through any of the four states. a) LBA=(001+10)0 b) LAB=01(001) c) LBB=(01) d) LBA=0(0010) The operation Perm(w), applied to a string w, is all strings that can be constructed by permuting the symbols of w in any order. For example, if w= 101 , then Perm(w) is all strings with two 1 's and one 0, i.e., Perm (w)={101, 110,011}. If L is a regular language, then Perm(L) is the union of Perm(w) taken over all w in L. For example, if L is the language L(01), then Perm(L) is all strings of 0 's and 1 's, i.e., L((0+1)). If L is regular, Perm(L) is sometimes regular, sometimes context-free but not regular, and sometimes not even context-free. Consider each of the following regular expressions R below, and decide whether Perm(L(R) ) is regular, context-free, or neither: 1. (01)* 2. 0+1 3. (012) 4. (01+2) a) Perm(L(0+1)) is regular. b) Perm(L((01))) is regular. c) Perm(L((01))) is not context-free. d) Perm(L((01+2))) is regular