Register

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 4

693 views

1 Answer

Best answer
13 votes
13 votes
$18 = 2 \times 9 = 2^{1} \times 9.$

For any integer $m = 2^k \times d$ where $d$ is odd, the minimal number of states in the DFA to recognize divisibility by $m$ is $k + d.$ So, answer here is $1+9 =10.$

Reference https://gateoverflow.in/blog/8651/minimum-number-states-dfa-accepting-binary-number-divisible
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
2 answers
1
gatecse asked Sep 29, 2020
475 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 9
The number of two state DFAs with a designated initial state and a designated final state that can be constructed over the alphabet set $\Sigma = \{0,1\}$ is _______
The number of two state DFAs with a designated initial state and a designated final state that can be constructed over the alphabet set $\Sigma = \{0,1\}$ is _______
User Avatar
4 votes
4 votes
2 answers
2
gatecse asked Sep 29, 2020
376 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 5
For $L=\{\varepsilon \},$ if the number of total and final states required in the minimal state deterministic finite automata to accept $L$ over $\Sigma = \{a,b\}$ are denoted by $a$ and $b$ respectively, then $a-b = $_____
For $L=\{\varepsilon \},$ if the number of total and final states required in the minimal state deterministic finite automata to accept $L$ over $\Sigma = \{a,b\}$ are de...
User Avatar
3 votes
3 votes
3 answers
3
gatecse asked Sep 29, 2020
353 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 6
In the DFA (not necessarily minimal) for a regular language $L$ over $\Sigma = \{a, b, c,d\},$ the minimum number of outgoing edges for any state is _____
In the DFA (not necessarily minimal) for a regular language $L$ over $\Sigma = \{a, b, c,d\},$ the minimum number of outgoing edges for any state is _____
User Avatar
4 votes
4 votes
2 answers
4
gatecse asked Sep 29, 2020
335 views
GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 11
The number of states, after the minimization of the below Deterministic Finite Automata is _______
The number of states, after the minimization of the below Deterministic Finite Automata is _______
User Avatar
Link Copied!