4. Construct an automata given the regular expression (0+1)*(00+01) ( 2 pts for representing the correct states, 3 pts for correct transitions)
5. For each of the following regular expressions, construct a DFA that recognizes it. 1. ((0 u 1)*0)* (1.5 pts) 2. (1010 0101 u 10 01)* (2 pts) 3. 0 u (00 u 000)* (1.5 pts)
6. Consider the language L = {0n1m0n1 m I m, n > 0}. (a) Give a high-level description of a deterministic Turing machine for L: (3pts) (b) Give a transition diagram of the Turing machine in a): (1 pt) (c) Is your Turing machine is a decider? Justify the answer (1pt)
7. Construct a deterministic finite automaton (DFA) A that accepts the language over the alphabet {a, b, (2.5 pts ) a)constituted by all strings that begin with a sequence of one or more a’s, and end with a b. E.g., aaabcbccaabb E L(A), while aaabcbcc 6E L(A), and bcbccaabb 6E L(A).
(b) Construct a regular expression E that generates the language over the alphabet {x, y, z} constituted by all strings in which each y is immediately followed by a z. (2.5 pts) E.g., xxyzzzxyzyzxx E L(E), while xxyzzzxyyzyzxx 6E L(E).
