The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes

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 (68.9k points)
retagged by | 1k views

1 Answer

+19 votes
Best answer
it is 3 states as we need a state each for length mod 3 = 0, 1 and 2.
answered by (219 points)
selected by

Can anybody please explain why 2 states is wrong answer ?

Please find the below diagram in reference to my query.


@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.
Yes now I understand the point.

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

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

32,693 questions
39,293 answers
36,701 users