4.6k 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$

edited | 4.6k views
+2
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 !

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

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

+2
hi praveen, how did u convert the above NFA to DFA? i am getting more numbers of states in DFA... :(
+6
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

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?

+2
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..
0

@Praveen Saini sir,

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

Can I take it as a formula, which I can apply for all ???

0
Why aren't we optimizing?

If we optimize, we would get 4 states.
0
SIR I HAVE PROBLEM,

AS U KNOW THERE IS RULE FOR CONVERTING NFA TO DFA ,BUT BY THAT PROCESS IF I MADE DFA THEN I GET 8 STATES .

SIR PLZ HELP ME BY MAKING DFA BY THAT PROCESS
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 (423 points)
0
Also mention that its complement will also require the same no. of states since the DFA is minimized.

when we do complementation of DFA then numbers of states remaining same....

by Junior (577 points)
contain 5 state

correct option B
by (11 points)