Theory Of Computer Science:

Question 2: 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 3 when divided by 5. Assume the standard binary encoding of integers. For example, the string 100100101 is in this language: It encodes the number 293. The strings 100100 and 11001 encode the numbers 36 and 25 and are not in this language.

b. (2 marks) The language of all binary strings that do not contain the substring 1010. So, 1011001011100101 is in this language; 1001100101000111001 is not, because of the highlighted occurrence of the substring abc.

c. (2 marks) The language of all binary strings with an even number of 0s or a number of 1s that is divisible by 4. This is the same language is in part (c) of Question 1.

Provide graphical representations of your DFA. You dont need to prove that your DFA is correct, but you must explain how you came up with this DFA, your intuition why it is correct. The easiest way to do this is to explain what each state of the DFA represents, as we did in class. Example: Consider the standard binary encoding of integers. The following DFA decides the language of all binary strings that represent integers that are divisible by 3 or 5: This DFA looks terribly complex (and indeed, the DFA you are asked to design are simpler), but with the right explanation of what the 16 states of this DFA represent, it is actually rather obvious that it is correct: The start state represents the situation when we havent read anything yet. Since the empty string does not represent any number, it is not an accepting state. The other states are organized into a 3x5 matrix. Each state encodes the remainder that the number read so far leaves modulo 3 and modulo 5.

The top row represents remainder 0 modulo 3, the row below it represents remainder 1 modulo 3, and the final row represents remainder 2 modulo 3. Similarly, the leftmost column represents remainder 0 modulo 5, the next column remainder 1 modulo 5, and so on until the last column, which represents remainder 4 modulo 5. Since we want to accept an input if it is divisible by 3 or 5, we need to accept if we end up in a state that represents remainder 0 modulo 3 or 5. Thus, the states in the top row and left column are accepting. All other states are not accepting. The transitions now reflect arithmetic modulo 3 and 5. Note that whenever we read another digit, thats the same as shifting the string read so far one bit to the left and then setting the the lowest bit in our number equal to 0 or 1. Thus, if we read a 0, this is the same as multiplying the number read so far by 2. Reading a 1 is the same as multiplying the current number by 2 and then adding 1. This logic immediately gives us all the transitions in this DFA. Here are two examples: Consider the top-left state, which represents remainder 0 modulo 3 and remainder 0 modulo 5. If we read a 0, then we multiply the current number by 2. Since the current number is divisible by both 3 and 5, it remains divisible by 3 and 5, so we stay in the top-left state. Therefore, for the character 0, we have a loop from the top-left state back to itself. If we read a 1, then we once again multiply the current number by 2 but then add 1 to it. Multiplying by 2 produces a number divisible by both 3 and 5, given that the current number is divisible by 3 and 5. Adding 1 then produces a number that leaves a remainder of 1 both modulo 3 and 5. Thus, we move diagonally to the state in the next row and next column, which represent remainder 1 modulo 3 and 5, respectively. As a more interesting example, consider the middle state, the one in the second row and third column. This state represents remainder 1 modulo 3 and remainder 2 modulo 5. Multiplying the current number by 2 then gives a number that leaves remainder 2 modulo 3 and remainder 4 modulo 5. These are represented by the bottom row and rightmost column, respectively, that is we transition to the bottom-right state. If we read a 1, then again the multiplication by 2 gives us a number that leaves a remainder of 2 modulo 3 and a remaindor of 4 modulo 5. Adding 1 to this number produces a number that leaves a remainder of 0 modulo 3 and a remainder of 0 modulo 5. Thus, we move to the top-left state.