edited by
366 views
2 votes
2 votes

The Minimal Finite Automata accepting the set of all strings over $(0+1)^*$ that do NOT have the sub-string $0001$ has:

  1. $5$ states
  2. $6$ states
  3. $7$ states
  4. $9$ states
edited by

1 Answer

Best answer
5 votes
5 votes

(A) is the correct answer!

i. Make a DFA to accept the language which contains the set of all strings over (0+1)* that have the sub-string 0001, it will have 5 states.
ii. find the complement of the machine made in step 1, it will have 5 states too! just convert final state into nonfinal and vice versa

 

edited by
Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,184 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
297 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
205 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4