edited by
614 views
1 votes
1 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 

edited by

1 Answer

0 votes
0 votes
if a string contains 011 then definitely 01 will automatically included.

hence make dfa containing 011 substring and then compliment the dfa.

therefore ans is  4

 

.

Related questions

0 votes
0 votes
0 answers
1
Magma asked Jan 15, 2019
521 views
Consider the following NFA M , over the alphabet {a}let L(M) be the language accepted by the NFA M . let $M'$ denote the machine obtained by the final and non final sta...
0 votes
0 votes
2 answers
3
prisonmatch asked Jan 6, 2019
1,182 views
How may Moore/Mealy m/c are possible with two states X & Y for the input alphabet {a, b} and output alphabet {0, 1} , where x is always the initial state?
0 votes
0 votes
2 answers
4
jhaanuj2108 asked Sep 26, 2018
620 views
The difference between the number of states in minimal DFA and minimal NFA, which accepts all strings end with 3rd bit as b is _____. [ Assume $\sum$ = {a,b} ]