Question 1. Assume the alphabet is {a,b,c}. In the following questions, give a regular expression that represents the described set. (15 Marks) a) The set of all strings over {a,b,c} containing only one a. b) The set of all strings over {a,b,c) that begins with bc and ends with ac. c) The set of all strings over {a,b,c) that contains the substings aa or bb. d) The set of all strings over {a,b,c} either starts and ends with b or starts and ends with e) The set of all strings over {a,b,c) starts with at least one b and ends with c immediately followed by at least one a. Question 2. Assume the alphabet is (a, b, c}. In the following questions, explain the language represented by the given regular expression. (15 Marks) c. a) (CU E) (EU) b) abb* c) (bb**bb) U (cc *cc) d) (bc")* e) *bab Question 3. Assume the alphabet is {a,b,c}. Convert the following regular expressions to an equivalent Nondeterministic Finite Automaton (NFA). (50 Marks). a) (ab U c)* ca b) a*(buc) c) bb(a*)c d) (ba)*c* e) (aa)* UbUc Question 4. This question concerns TM, M3, whose description and state diagram appear in Example 3.7 (Page 144 in the textbook, as well as it was shown as the first example in the class). **Turing machine (TM) that decides A = { the language consisting of all strings of Os whose length is a power of 2." Give the sequence of configurations that M, goes when started with 4,000 configuration. Show the tape contents, head position and configuration for each transition. (20 Marks)