The Gateway to Computer Science Excellence
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 | 135 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.

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,833 questions
57,737 answers
107,989 users