The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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 

My Answer:

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 

in Theory of Computation by (75 points)
edited by | 98 views

Isn't this the DFA for the given language and its complement?


Why string  01 is accepted??

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

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

Please log in or register to answer this question.

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
50,288 questions
55,719 answers
90,123 users