retagged by
780 views
2 votes
2 votes

please explain answer given is 5

retagged by

1 Answer

0 votes
0 votes

 

lets us suppose we have to make DFA of whose integer equivalent is divisible by  x

then write the x in the form of  $2^{k}*m$ where m is odd no

then the minimum no of state in the DFA  will be k+m

now we will understand  it by using examples  

ex1    divisible by 16 

then write 16 in form of  $2^{k}*m$  ( $2^{4}*1$)  so 4+1=5 answer

ex2    divisible by 12

then write 12 in form of  $2^{k}*m$  ( $2^{2}*3$)  so 2+3=5 answer

ex3    divisible by 18

then write 18 in form of  $2^{k}*m$  ( $2^{1}*9$)  so 1+9=10 answer

 

Related questions

2 votes
2 votes
2 answers
1
0 votes
0 votes
2 answers
3
Manuj_og asked May 2, 2023
210 views
on seeing a dfa how can we predict the number of states in it?
0 votes
0 votes
1 answer
4
Dknights asked Nov 19, 2022
318 views
can we solve it with a minimum of 4 states?