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

+20 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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,111 questions

44,694 answers

127,237 comments

43,753 users