1.3k 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 $\}.$
retagged | 1.3k 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 .....

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

Ans...

here q0 is the initial state and final state

answered by Junior (687 points)
0

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