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.

Answer 1

I assume that the input is presented starting from the most significant digit.

And I assume $ marking the end of input.

The dfa has the following 7 states with their interpretation:

accept (final state, if entered then the string is divisible by 5)

reject (final state, if entered then the string is not divisible by 5)

s₀ (all the digits seen so far represent a number that is 0 mod 5)

s₁ (all the digits seen so far represent a number that is 1 mod 5)

s₂ (all the digits seen so far represent a number that is 2 mod 5)

s₃ (all the digits seen so far represent a number that is 3 mod 5)

s₄ (all the digits seen so far represent a number that is 4 mod 5)

The initial state is s₀ .

The transitions are:

Input $:

The current state s_r means that the number seen so far is r mod 5,

so depending on r, we accept or reject.

s₀ -- $ --> accept

s₁ -- $ --> reject

s₂ -- $ --> reject

s₃ -- $ --> reject

s₄ -- $ --> reject

Input 0:

The number represented by the digits seen so far is being multiplied by 2.

And therefore so is the remainder.

s₀ -- 0 --> s₀

s₁ -- 0 --> s₂

s₂ -- 0 --> s₄

s₃ -- 0 --> s₁

s₄ -- 0 --> s₃

Input 1:

Like input 0, but 1 is being added as well.

s₀ -- 1 --> s₁

s₁ -- 1 --> s₃

s₂ -- 1 --> s₀

s₃ -- 1 --> s₂

s₄ -- 1 --> s₄