retagged by
11,675 views
36 votes
36 votes
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:

$L=\{w \in  \{0, 1\}^* \mid w$  interpreted as binary number (ignoring the leading zeros) is divisible by five $\}.$
retagged by

2 Answers

Best answer
51 votes
51 votes

Suppose we have decimal no $3$ after that we get a symbol $2$ . it becomes $32$ as  $3 x 10 +2 = 32 $

In binary if we have $10$ ( i.e $2$ in decimal say old no) and after that we get symbol $1$ it become $101$( i.e $5$ in decimal say new no ) 

$ 2$ (old no.) $ \times 2$( base)  $+1$( input symbol) $= 5$ (new no.)

Now in the given problem, binary no is divisible by $5$ , i.e $0,101,1010,1111..... $

We need $5$ states in DFA , $0,1,2,3$ and $4$ .Each state represent remainder that comes when we divide no by $5$.

Input symbol $=\{0,1\}$

We get the transition:

[Old state $\times$ base $+$ input symbol] mod $5 =$ New state    , where base is $2$ 

$[0 \times 2 + 0]mod \ 5 = 0$           $[1  \times 2 + 0]mod \ 5 = 2$         $[2  \times 2 + 0]mod \ 5 = 4$       

$[0 \times 2 + 1]mod  \ 5 = 1$           $[1  \times 2 + 1]mod \ 5 = 3$         $[2  \times 2 + 1]mod \ 5 = 0$       

$[3  \times 2 + 0]mod \ 5 = 1$           $[4  \times 2 + 0]mod \ 5 = 3$

$[3  \times 2 + 1]mod \ 5 = 2$           $[4  \times 2 + 1]mod \ 5 = 4 $

edited by

Related questions

39 votes
39 votes
4 answers
1
Kathleen asked Sep 25, 2014
17,223 views
Let $L$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimal state deterministic finite state automaton accepting $L$...
24 votes
24 votes
1 answer
3
Kathleen asked Sep 29, 2014
14,252 views
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...