in Theory of Computation edited by
11,337 views
32 votes
32 votes

A minimum state deterministic finite automaton accepting the language

$L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$   has

  1. $15$ states
  2. $11$ states
  3. $10$ states
  4. $9$ states
in Theory of Computation edited by
11.3k views

4 Answers

37 votes
37 votes
Best answer

Answer will be (A) $15$ states.

We need a separate state for #$0 = 0, 1, 2$ and #$1 = 0, 1, 2, 3, 4$ giving total minimum number of states $= 3 * 5 = 15. $

This is a direct consequence of Myhill-Nerode theorem.

http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf

edited by
by

4 Comments

@AHWAN  length of string    and      no. of 'a' & 'b' both are different case .

in case of length of string divisible by 2 and 4 we take L.C.M and we get 4.

IN CASE of no. of 'a' divisible by 2 and no. 'b' divisible by 4  we take multiply and we get 8.
4
4
If Anyone came up with the answer 9. That's valid if the question is for divisible by 3 OR divisible by 5
–1
–1

No,  No.of states remains same even in case of ‘OR’. Only final states will be changed in ‘OR’ case.

Refer this discussion

https://gateoverflow.in/723/gate2001-2-5

 

0
0
5 votes
5 votes

total states will be 15

 

2 votes
2 votes
Given that number of 0's and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15.

As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required) , so product automata will require (3 × 5=15 states).

1 comment

Wrong logic 3 0's are also accepted which is not divisible by 15. LCM logic is not required in this question.
0
0
0 votes
0 votes
Most of the times the answer the answer for number of states  is cartesian product one dfa going horizontally and the other one vertically
Answer:

Related questions