The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.5k 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 (59.7k points)
retagged by | 1.5k views
0

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.

2 Answers

+33 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.4k points)
edited by
0
Then for designing a DFA divisible by n, we require minimum of n states?
+2
Not in case of even n.
0
why not in case of even n??
+1
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
+1
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.
+2 votes

Ans...

here q0 is the initial state and final state

answered by Junior (807 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

44,459 questions
49,917 answers
165,414 comments
65,897 users