Design DFA which checks whether a given binary number is divisible by 3

SOLUTION:

∑={0,1}

Decimal No.	Binary No.	Remainder	States representing Remainders
0	0000	0	q0
1	0001	1	q1
2	0010	2	q2
3	0011	0	q0
4	0100	1	q1
5	0101	2	q2
6	0110	0	q0
7	0111	1	q1
8	1000	2	q2

Ø  So DFA can be Q={ q₀ , q₁ , q₂},∑={0,1}, q₀={ q₀},F={ q₀} and δ is given by the table

1)Transition diagram:

   2)Transition Table:

Present State	Next State
	Input 0	Input 1
à *q0	q0	q1
q1	q2	q0
q2	q1	q2

Since the number should be divisible by 3, so final state will be q₀

  3)Transition function:

δ( q₀, 0)= q₀    ,δ (q₀,1)= q₁

            δ( q₁, 0)= q₂    ,δ (q₁,1)= q₀   

δ( q₂, 0)= q₁    ,δ (q₂,1)= q₂