1. (20 marks) Compute the languages L1 = {the set of all strings over the alphabet {0,1} that begin with 100} L2 = {the set of all strings over the alphabet {0,1} that end with 0100} L3 = {the set of all strings over the alphabet {0,1} that begin with 1010} For each of the languages (a) L1 = Lin L2, and (b) L5 = L3nL2 give a DFA for accepting it over the alphabet {0,1}. 2. (40 marks) Compute the following languages over the alphabet {0,1}: (a) the set of all strings consisting of alternating groups of 1 and 101 (1 and 101 alternates at least once); (b) the set of all strings whose forth symbol from the right end is a 0; (c) the set of strings that either begin, or end (or both) with 110; (d) the set of strings such that the number of O's is divisible by six, and the number of l's is divisible by five. and for each case give a DFA accepting it. 3. (20 marks) Give DFA's accepting the following languages over the alphabet = {0,1,3,4,6}: (a) the set of all strings beginning with a 1, 3 or 6, that, when the string is interpreted as an integer in base 7, is a multiple of 4 plus 1. For example: . strings 1, 16, 111, 166, 331, 643, 3646, 3334, 36411 and 36433 are in the language; the strings 10, 00,011, 0010, 36, 13, 23, 113, 1313, 2347,2, 21, 161, 3333, 606, 44, 41, and 041 are not. (b) The set of all strings that ends with an 1, 3, or 6 and when the string is interpreted in reverse as an integer in base 7. is a multiple of 4 plus 1. Examples of strings in the language are 1, 61, 111, 661, 133, 346, 6463, 4333, 11463 and 33463 Examples of strings that are not in the language are: 01, 00,110, 0100, 63, 31, 32, 311, 3131, 7432, 2, 12, 161, 3333, 606, 44, 14, and 140