The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.5k views

The smallest finite automaton which accepts the language $\{x |$ length of $x$ is divisible by $3\}$ has

  1. $2$ states
  2. $3$ states
  3. $4$ states
  4. $5$ states
asked in Theory of Computation by Veteran (59.6k points)
edited by | 1.5k views
0
Modulo 3 gives remainder as ( 0, 1, 2 )

3 states needed

3 Answers

+20 votes
Best answer

Answer (B). It is $3$ states as we need a state each for length mod $3 = 0, 1$ and $2$.

answered by (191 points)
edited by
0

Can anybody please explain why 2 states is wrong answer ?

Please find the below diagram in reference to my query.

0
@Sid Try string "1". It will be accepted by your machine though length of string isn't divisible by 3.

General formula: a (mod n) then we will have n states in minimal DFA, which is unique. If DFA isn't minimal we may have more number of states.
0
Yes now I understand the point.

My answer would be applicable for length as odd number rather than as divisible by 3.
0
@Sid Yes for the odd number it is applicable with q0 as starting state.
0

In the question it is saying {x | length of the x is divisible by 3}  not the x itself is divisible by 3 . So, the

answer should be B. 3 states but diagram would be 

 

0

what about length 0,why initial state is final state?

+1 vote

Option B is Correct

answered by Active (3.2k points)
0 votes

Correct option is B. 

answered by Junior (831 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,619 questions
48,614 answers
155,881 comments
63,863 users