(1) Let D = fw j w contains an even number of a’s and an odd number of b’s and does not contain the substring abg Give a DFA with five states that recognizes D and a regular expression that defines D. (Suggestion: think of a simpler way to describe D first.) (2) Let L1 be the set of strings over fa; bg∗ that contain at least two a’s and L2 be the set of strings over fa; bg∗ that contain at most two a’s. (a) Give a DFA for L1 (b) Give a DFA for L2 (c) Using the product construction shown in class, give a DFA for L1 [ L2. Show all states, even those that are inaccessible. (3) Use the construction given in class to convert the following NFA to a DFA. Give a transition table and a transition diagram for the resulting DFA. 3 start 1 2 ? a a a; b b (4) Use the procedure given in class to convert the following regular expression to an NFA (((00)∗(11)) [ 01)∗ (5) Use the procedure given in class to convert the following DFA to a regular expression 12 HOMEWORK 1{CSC 320 FALL 2015 start 1 2 a b a b (6) Give a construction that shows that if A and B are regular, so is A=B = fw j wx 2 A for some x 2 Bg (7) For languages A and B, define the shuffle of A and B to be the language fw j w = a1b1 : : : akbk; where a1 : : : ak 2 A and b1 : : : bk 2 B; and ai; bi 2 Σ∗; 1 ≤ i ≤ kg Give a construction that shows that the regular languages are closed under shuffle.
