CODEWITHSUNDEEP
theoryproofautomatacomputation-theorydfa
sukhi
sukhi

Reputation: 11

Does this DFA satisfy the complement of the given language?

I got this challenge:

Given 𝐿 = { 𝑤 ∊ {0, 1}* : 01 is a substring of 𝑤 }

Show 𝐿 compliment is regular.

My understanding is that a DFA for the compliment of this language would need to reject 01 substrings.

Here is my DFA for L(M) = L compliment:

MY DFA

Does my DFA correctly accept the compliment language?

Upvotes: -2

Views: 52

Answers (1)

trincot
trincot

Reputation: 350270

It looks fine, except that it wouldn't accept an empty input, which to my understanding should be accepted.

With that modification there is no reason any more to distinguish between q0 and q2: they can be merged into an accepted state:

enter image description here

Upvotes: 1

Related Questions