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

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

+1

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 .....

0

yes.|E|=k mod n or |E| mod n=k where n will be the no of states and k decides which no of state among n is final state.

0

Language that accepts **binary strings whose decimal equivalent is divisible by n.**

minimal dfa for this language does not always have n states..

https://gateoverflow.in/263964/gatebook-2019-toc1-7

For binary strings--

$\bullet$ if n is odd then we need n states in mDFA.

$\bullet$ if n is a power of 2 (let's say $2^k$ ) then we need k+1 states.

+35 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

0

no only state 5 is the final state.

ignoring the leading zeros, is given in the question....so state 0 is not the final state.

That's what I was saying so long....

M i wrong????

ignoring the leading zeros, is given in the question....so state 0 is not the final state.

That's what I was saying so long....

M i wrong????

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,541 questions

54,071 answers

187,187 comments

70,978 users