The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Ques:-  Let ∑= {0, 1} What will be the number of states in minimal DFA, if the Binary number string is congruent to (mod 8)?

*[ Can anybody explain this as I am getting 8 states for this since remainders will be 8 (0,1,2,3,4,5,6,7). But the answer is 4].
asked in Theory of Computation by (165 points) | 229 views
when you draw transaction table you get 8 states out of which 4 states are equal states, so that MDFA contain 4 states.
what does binary number string mean here?
Binary number string means strings can form using only the input 0,1.(strings having all combination of 0,1)

3 Answers

+4 votes

$4$ states.

answered by Active (1k points)
there is a flaw in ur state ur states also accepts the binary numbers divisible by 16 {ends with 4 0's}

to make it correct remove the loop on final state with 0 and make the transaction to initial state like {state-4 ----0------>initial state}
0 votes

MDFA, for binary strings congruent to (mod 8) for input $\sum$(0,1) as follow:

transcation table:

                   states                      0                     1
                     Q0                      Q0                    Q1
                     Q1                      Q2                    Q3
                     Q2                      Q4                    Q5
                     Q3                      Q6                    Q7
                     Q4                      Q0                    Q1
                      Q5                      Q2                    Q3
                      Q6                      Q4                    Q5
                      Q7                      Q6                    Q7

In here, binary string r(mod n),number of states is depends on remainder & final state is Qr.

from table 4 equal states such as Q0 =Q4 ,Q1 =Q5 ,Q2 =Q6,Q3 =Q7.

So MDFA contain 4 states.

answered by Boss (13.8k points)
Thanks for the answer :)

Hi Thanks for the answer but recently I had discovered a flaw in your answer.


If you use 'Minimization of DFA' technique where we make 0equivalence,1equivalence states. You will not get q0 = q4, q1=q5,... as you have mentioned.

Your answer is correct but not the method.

The minimized DFA states after 'Minimization of DFA' are [q0],[q4],[q1,q3,q5,q7],[q2,q6].
where q0 is initial and final state and according to these minimized states we can say that "q0 and q4 are independent" and "q1,q3,q5,q7 are equal" and also "q2 and q6 are equal".

Please correct me if I am wrong.



0 votes
it is in the form of 2^n

then minimal DFA contain n+1 states

here 4 states

suppose if the number is in odd like 3 ,5,7,9..

minimal DFA contain n states

it is valid only for the binary string
answered by (307 points)
edited by

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

46,668 questions
51,139 answers
66,556 users