Register

Ace Test Series: Theory of Computation - Minimal State Automata

• edited by
426 views

1 Answer

Best answer
2 votes
2 votes

If we make a DFA accepting binary strings divisible by 4 then it takes 4 states such as

state 0 :  remainder 0 accepting 4,8,12,16,20,24,28,32,36,40...

state 1:  remainder 1 accepting 1,5,9,13,17...

state 2: reaminder 2 accepting 2,6,10,14,18...

state 3: remainder 3 accepting 3,7,11,15,19....

This DFA is also accepting all stings divisible by 8 also..Thus 

GCD (4,8) = 4

Even this is a pattern for every question like this for any other number such as divisible by 3,6 will take GCD (3,6) states.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
Soumya29 asked Jan 6, 2019
605 views
Testbook Test Series: Theory of Computation - Minimal State Automata
$Que-$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______. Approach ?
$Que-$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______.Approach ?
User Avatar
2 votes
2 votes
1 answer
3
Purple asked Jan 28, 2016
13,912 views
Number of final state require to accept Φ in minimal finite automata.
Number of final state require to accept Φ in minimal finite automata. a) 1 b) 2 c) 3 d) None of the mentioned
Number of final state require to accept Φ in minimal finite automata.a) 1b) 2c) 3d) None of the mentioned
User Avatar
0 votes
0 votes
1 answer
4
Pranav Madhani asked Oct 26, 2017
448 views
MadeEasy WorkBook: Theory of Computation - Minimum State Automata
IF a number is divisible by say any integer X then what will be the minimum states required in DFA?
IF a number is divisible by say any integer X then what will be the minimum states required in DFA?
User Avatar
Link Copied!