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

3 states needed

3 states needed

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

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

- $2$ states
- $3$ states
- $4$ states
- $5$ states

+21 votes

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.

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.

My answer would be applicable for length as odd number rather than as divisible by 3.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,261 answers

182,169 comments

67,679 users