edited by
16,931 views
55 votes
55 votes

Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)?

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

5 Answers

Best answer
64 votes
64 votes

First we can draw dfa for $L$ which has $5$ states after that for $L$ compliment we will convert all final to non final and all non final to final so, total states is $5$.

Anwer is option B.

edited by
16 votes
16 votes
For any substring pattern we need n+1 states, where n is the cardinality of the substring i.e. |w|=n

Here |0011|=4 . So we require 4+1=5 states
1 votes
1 votes

No. of states in DFA accepting L and complement of L is same. So let's draw minimal DFA for L,

So, 5 states are there.

 

Answer:

Related questions

36 votes
36 votes
6 answers
1
go_editor asked Feb 13, 2015
15,511 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
44 votes
44 votes
2 answers
3
65 votes
65 votes
12 answers
4