1,364 views
2 votes
2 votes
Let Σ= {0, 1} What will be the number of states in minimal DFA, if the Binary number string is congruent to (mod 8). A. 8 B. 9 C. 7 D. 4

4 Answers

2 votes
2 votes

One Straight Answer can be derived from this..
x mod m , if m can be written in the form of 2^n then the number of states equals to n+1
Second  is what is mentioned in @Praveen Comment, 

4 of these states will get minimized. it is just as all strings ending with 000

Thus Answer is Option D)

 

0 votes
0 votes
option D

any binary number having 3 right most bits 0 will be divisible by 8 .why? because if you put 1 in any place after 3rd bit that will be divisible by 8 .(8,16,32..) adding those weights divisible by 8. so 4 is the correct answer
0 votes
0 votes
I think correct ans is 8

because the value on n which is going to divide from 8 is not given and n can be any no

so remainders can be from 0 to 7 ,,,,, if we choose 4 then input will In input will be in between from 0000 to 1111 ....  

n mod 8 , So 8 states are required
edited by

Related questions

0 votes
0 votes
2 answers
2
0 votes
0 votes
0 answers
4
koushriek asked May 19, 2022
1,281 views
Examples of accepted words: 1011, 101101, 1111Example of non-accepted words: 101, 1001, 010The solution says the min-DFA contains 5 states but I could only do it in 4. Am...