The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
3.9k views

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
0
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
0
Can you please draw the dfa for this?
+53

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

+1
hi praveen, how did u convert the above NFA to DFA? i am getting more numbers of states in DFA... :(
+4
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
0
yes u r correct..thank u..:)
+1
Aren't there only four final states in the DFA that are accepting L(bar)
+2
@lifeisshubh

yes, right but total no of states required is 5
0
i am getting 6 states and 2 final states in DFA how do you convert it into dfa of 5 states. PLZ explain
0
Is it mandatory to show dead state ?
Shouldn't the answer be 4 (not considering the 5th state?) ?
0
Yes, in DFA, we must have transition for each symbol on each state, $Q \times \Sigma \rightarrow Q $.
0
@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?
0

habedo007 

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

+2
@habed0007

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

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?

+1
Yes.
0
While converting nfa to dfa I am getting 8 states by using the conversion method of nfa to dfa.
0
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?
0

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

0
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)
0
Also mention that its complement will also require the same no. of states since the DFA is minimized.
Answer:

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
190,487 comments
85,105 users