Question 3: Finite Automata (6 Marks) Construct deterministic finite automata that decide the following languages: a. (2 marks) The language of all binary strings that leave a remainder of 2 when divided by 4. Assume the standard binary encoding of integers. For example, the string 100100110 is in the language: It encodes the number 294. The strings 100100 and 11001 encode the numbers 36 and 25 and are not in the language. b. (2 marks) The language of all strings over the alphabet {a,b,c} that do not contain the substring abc. So, abacbabac is in the language; abacbabcaabac is not, because of the highlighted occurrence of the substring abc. C. (2 marks) The language of all binary strings with an odd number of Os or a number of 1s that is divisible by 3. The strings 011001110110, 011001101001, and 0110011010010 belong to the language: 011001110110 contains an odd number of Os, 011001101001 contains a number of 1s divisible by 3, and 0110011010010 satisfies both conditions. The string 01101001100 is not in the language because it contains an even number of Os and the number of 1s is not divisible by 3