edited by
296 views
1 votes
1 votes

How many states are there in the minimal DFA that accept the following language?

$L= \{x \mid x$ is a binary string with number of $0$'s divisible by $2$ and number of $1$'s divisible by $3 \}$

  1. $6$
  2. $5$
  3. $3$
  4. $2$
edited by

1 Answer

Best answer
3 votes
3 votes
While checking the divisibility of a number by 2, the possible cases are:- remainder 0 or 1 i.e. 2 cases. Similarly, for checking divisibility by 3, there are 3 possible cases, remainder 0,1 or 2. Therefore in total we have 2*3 = 6 possible states to be drawn in the minimal DFA.
selected by
Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,183 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
296 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
204 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4