#self doubt

Question

MIN DFA of {w: w contains an even number of 0s and exactly two 1s}

 

MIN DFA of {w: w contains an even number of 0s or exactly two 1s} ex 111 is valid

Answer 1

[It is an example of Compound Automata.]

Answer 2

You can create states using all the possibilities i.e,

S1 : (Seen even 0s, Seen zero 1s) Will be initial state as in empty string there are zeros 1s and even 0s

S2: (Seen odd 0s, Seen zero 1s)

S3: (Seen even 0s, Seen one 1s)

S4: (Seen odd 0s, Seen one 1s)

S5: (Seen even 0s, Seen two 1s)

S6: (Seen odd 0s, Seen two 1s)

S7: (Seen even 0s, Seen more than two 1s)

S8: (Seen odd 0s, Seen more than two 1s)

 

Then you can add transitions appropriately, and make the states you want as final

 

For even number of 0s and exactly two 1s, the only possibility is in {S5}. (S7 and S8 can be joined in one possibility in this case)

For even number of 0s or exactly two ones, the possibility is in

Possibility if even zeros : {S1, S3, S5, S7}

Possibility of exactly two 1s: {S5, S6}

So the union of these will be the final states

 

Edit: There will be a self loop in S8 on input 1