5,018 views

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

1. $2$ states
2. $3$ states
3. $4$ states
4. $5$ states

1 comment

Modulo 3 gives remainder as ( 0, 1, 2 )

3 states needed

Subscribe to GO Classes for GATE CSE 2022

Correct Option: B

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

by

Please find the below diagram in reference to my query.

edited by
@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.
edited

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

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

because 0 mod 3 =0

by