The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.9k views
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 $\}.$
asked in Theory of Computation by Veteran (52k points)
retagged by | 1.9k views
+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 ....

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

Ref:- https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n#

2 Answers

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

answered by Veteran (55.8k points)
edited by
+1
Then for designing a DFA divisible by n, we require minimum of n states?
+5
Not in case of even n.
+1
why not in case of even n??
+3
some of them get minimized
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).
0
then what is the given DFA doing? Or did you interpret the leading zeroes as going to a dead state?
0
No, sir  

I mean leading zero will loop in the first state...i,e 0th state.

Do i interpret it wrong?
0
that's the given DFA rt?
0
sir can u tell me.How I can attach a image here?

I am unable to that.
0

I....

+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
missed these two transitions:

state 4 on 0 goes to state 3

state 5 on 1 goes to state 1
0
Then state 5 and state 0 both will become equivalent. And I hope both states 5,0 are finals too
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????
0
actually 0 is also divisible by 5 (or by any num). so state 0 should be final too
+2
yes,  for designing a DFA divisible by n, then total n states required. each state represent remainder ( 0 to n-1 remainder ) that comes when we divide no by n.
0
Since initial state is the final state here, so this will accept ⋵  (epsilon) too.. but ⋵
is not a part of the language L.
+3 votes

Ans...

here q0 is the initial state and final state

answered by Junior (851 points)
0

 will help in better understanding above described method...........

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,071 answers
187,187 comments
70,978 users