made easy mock1

Question

let L={set of all strings over {0,1}* , containing 01 and 011 as the substring }

number of states in the minimal DFA of L’ is?

i’m getting 3. please confirm if you are getting 3 or 4. 

Comments

But if we make a DFA that accepts strings containing 011, and then take its complement, then the complemented DFA accepts strings containing '01' (but not those which contain 011) as a substring

Whereas, since L = strings containing 01 and 011 as a substring, shouldn't L' = strings which do NOT contain 01 and 011 as substrings?

 

This is the DFA for L

 

This is its complement, which accepts strings with 01 as a substring:

 

 

And this is a DFA that accepts strings which do not have 01 and 011 as substrings, and it has only 3 states, not 4

 

So shouldn't the answer be 3?

---

no 4 is the correct answer.

i also thought like you initially, but look at the question carefully...

they have given L as (01 and 011) as the substring.

if we complement (01 and 011), we will get not containing (01 or 011) as the substring.. i.e; (no-01 or no-011).

so this can be satisfied using 4 states.

in 3 states, what we are getting is (n0-01 and n0-011), which would be true if our original dfa would be (01 or 011).

---

Ahhh that's right, thank you so much