edited by
11,429 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
edited by

4 Answers

Best answer
37 votes
37 votes

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
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).
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

27 votes
27 votes
3 answers
1
go_editor asked Apr 23, 2016
8,415 views
Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$
43 votes
43 votes
6 answers
2
Kathleen asked Sep 21, 2014
13,287 views
Consider the following Finite State Automaton:The language accepted by this automaton is given by the regular expression$b^*ab^*ab^*ab^*$$(a + b)^*$$b^*a(a+b)^*$$b^*ab^*a...
39 votes
39 votes
2 answers
3
Kathleen asked Sep 21, 2014
14,054 views
Which of the following languages is regular?$\left\{ww^R \mid w \in \{0, 1\}^+\right\}$$\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$$\left\{wxw^R \mid x, w \in \{0, 1\}...
26 votes
26 votes
4 answers
4
Kathleen asked Sep 21, 2014
8,321 views
The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:not recursiveis recursive and is a deterministic CFLis a regular langu...