Question

1. Construct a dfa that accepts strings on {0, 1} if and only if the value of the string, interpreted as a binary representation of an integer, is zero modulo five. For example, 0101 and 1111, representing the integers 5 and 15, respectively, are to be accepted.

Answer 1

Here is procedure to build this dfa :

• To build this DFA, you must realize what happens upon reading a new character in terms of multiplication.
• If we are adding a 0 , it means we are multiplying our current number by 2 (this is a left shift operation). If we are adding a 1 , it means we are multiplying our current by 2 and adding 1.
• To make sure it is divisible by 5, we have to operate mod 5 and we should accept s only when s mod 5 = 0 when it is interpreted as a binary number(and it begins with 1)
• We also have to construct seperate states for start and 0 mod 5. This is why because if they are same states then we would go to trap state after reading a 0.
• But if we already read part of string that started with 1 and which was equivalent to 0 mod 5 then our DFA would trap but it should not. Thus, two states should need to be made(S and 0 in the below diagram) to prevent this error from occuring.

DFA :

Like, if this helped :)