computation-theorydfacomputation

DFA for all binary strings having even number of 0's or contains exactly two 1's


I'm trying to solve this challenge:

Design a DFA for all binary strings having an even number of 0's or containing exactly two 1's

I'm a bit confused with this question. I had tried to come up with a solution myself, referencing a few similar questions here and there, but I'm not sure if this is correct at all. Building an NFA to this is easy, but DFA is so confusing to me. I've inserted an image below of what I've done, but I don't know if it's right.

Solution that I've done:

DFA for each language:

DFA for each language:

Combined DFA by applying union rule where F = (F1 x Q2) U (Q1 x F2), where Q1 = {A, B}, Q2 = {C, D, E, F} and F1 = {A}, F2 = {E}. Therefore, our accepting states are: F = {AC, AD, AE, AF, BE} and our transition graph is defined as follows:

Combined DFA

I don't know if there was a need for including the dead/trap state F, but I had read a similar question doing the same thing, so I just followed it. Is there a reason why F is included? And is there a way to do the problem without using it?


Solution

  • By taking the union you have designed a DFA that accepts the union of the two languages, i.e. it accepts an input when it has an even number of "0", or it has exactly two "1" (or both). If that is what you need, then you have the correct DFA.

    But if you need the intersection of both languages, then 𝐹 = {𝐴𝐸}.

    In that case, in your final diagram, only the state 𝐴𝐸 should be an accepting state. None of the other states are accepting states.

    The final state diagram can then be simplified by merging states 𝐴𝐹 and 𝐵𝐹 into just state 𝐹 which is like a sink: from 𝐹 both 0 and 1 will transition to 𝐹.

    enter image description here

    Difference union and intersection

    Given two regular languages 𝐴 and 𝐵 (they could be defined by DFAs), we have:

    Just make sure you have the correct interpretation of this DFA challenge.