I hav forgot from where i read it ...

**The minimum DFA that accept all base "M" system which are divisible by "N" contains N state ....**

**Co**rrect me if i am wrong .....

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 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 $\}.$

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

+30 votes

Best answer

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 $

0

@Arjun sir

Ignoring the leading zeros is given in question, So shouldn't it be 6 state from state 0(not final state),1,2,3,4,5(final state).

Ignoring the leading zeros is given in question, So shouldn't it be 6 state from state 0(not final state),1,2,3,4,5(final state).

0

0

+1

@ ana , any binary number starting with more than 4 1's will not be accepted by above DFA, say 1111101, i,e 125

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,080 questions

45,572 answers

132,069 comments

49,047 users