The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 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$
in Theory of Computation by Veteran (99.6k points)
edited by | 3.9k views
Note: In this problem no need to draw NFA first and then minimize,instead try to draw DFA at first place it would be simple and solves the problem in less time !

2 Answers

+38 votes
Best answer

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.

by Active (5k points)
edited by
Can you please draw the dfa for this?

NFA for L = (0+1)*0011(0+1)*   [ all strings that contain 0011 as substring]

Convert NFA to DFA

DFA for L = (0+1)*0011(0+1)*   [ all strings that contain 0011 as substring]

DFA for $\bar{L}$ (complement of L)   that doesn't contain 0011 as subtring

Note : No need to do this in such question DFA that contain substring having n length will have n+1 states and same with complement

hi praveen, how did u convert the above NFA to DFA? i am getting more numbers of states in DFA... :(
few of them get minimized, look carefully at final states in table you get after NFA to DFA conversion I am sure final states will get minimized to one final state
yes u r correct..thank u..:)
Aren't there only four final states in the DFA that are accepting L(bar)

yes, right but total no of states required is 5
i am getting 6 states and 2 final states in DFA how do you convert it into dfa of 5 states. PLZ explain
Is it mandatory to show dead state ?
Shouldn't the answer be 4 (not considering the 5th state?) ?
Yes, in DFA, we must have transition for each symbol on each state, $Q \times \Sigma \rightarrow Q $.
@Praveen Saini sir Isn't it true that for an NFA with $n$ states we have its equivalent minimized DFA having $2^n$ states? Then shouldn't this NFA's DFA contain $2^5$ states?


NFA(n-states) ->DFA(2n) means it burst  case DFA could have 2n  not for always...


No, it is maximum up to $2^n$
@Praveen Saini sir thank you for correcting me.

Praveen Saini sir,

By using this method for complement of a language:

 To construct the DFA D that accepts the complement of L, simply convert each accepting state in A into a non-accepting state in D and convert each non-accepting state in A into an accept state in D.

if DFA D is minimized then is it always guranteed that reversal of dfa D' will be also always minimized?

While converting nfa to dfa I am getting 8 states by using the conversion method of nfa to dfa.
Hi Praveen,

If we minimize the Regular Expression  (0+1)*0011(0+1)* it becomes (0+1)*0011 (R*R*=R*) and proceed. Is it necessary that we show transition on last state of NFA?

, language containing 0011 as a substring is different from language ending with 0011.

Yeah me too..
+4 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
by (365 points)
Also mention that its complement will also require the same no. of states since the DFA is minimized.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,984 questions
55,135 answers
85,105 users