3,149 views
0 votes
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].

3 Answers

5 votes
5 votes

$4$ states.

1 votes
1 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
edited by
0 votes
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.

Related questions

1 votes
1 votes
1 answer
2
kislaya Pant asked May 8, 2018
1,063 views
Ques:- What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts with “aa” and length of the string is not congruent to 0 (mod 4)....
3 votes
3 votes
1 answer
3
2 votes
2 votes
1 answer
4
rahul sharma 5 asked Nov 9, 2017
936 views
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}