98 views

Let L = {w| w ∈ {0,1}*; w contains 01 and 011 as substring}. The number of states in the minimal DFA corresponding to the complement of L is equal to Correct if I am wrong. Its complement will be all strings which don’t have 01 as substring. so if we make its dfa then minimum number of states will be 3.

Answer given is 4

edited | 98 views
0

Isn't this the DFA for the given language and its complement? 0
Why string  01 is accepted??
+1

P = contains 01

Q = contains 011

Given $L = P \wedge Q$ i.e. any string of $L$ should have both 01 and 011 as its substring.

The complement of it which means $\overline{L}$ should NOT have both 01 and 011 as its substring (It can have either one of them. But if it includes '011' then it also includes '01'. Hence, 011 cannot be included.).

$\overline{L} = \overline{P} \vee\overline{Q}$

It can also be restated as  $\overline{L}$ does not contain 01 or $\overline{L}$ does not contain 011.

Quite confusing Maybe :P

0
Oh ok simple boolean concept but yeah somewhat confusing. Thanks Great explanation

2