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

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

+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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,737 answers

199,467 comments

107,989 users