Finding the union, subtraction, and intersection of two DFAs

Question

I recently solved problem of finding union of two DFAs and came up with some observations. I need confirmation about them along with some other facts:

1. I can prepare the union, subtraction and intersection DFA of two DFAs by preparing their product automaton and then suitably choosing final state. If $A_1$ and $A_2$ are non final states of DFA₁ and DFA₂ respectively and $F_1$ and $F_2$ are final states of DFA₁ and DFA₂ respectively, then,

   • For union of the DFAs, any state having any final state will be final:
     $A_1F_2, F_1A_2$ and $F_1F_2$.
   • For intersection of the DFAs, any state having both final states will be final:
     $F_1F_2$
   • For subtraction DFA₁-DFA₂, state having DFA₁'s final state but non final state of DFA₂ will be final: $F_1A_2$

2. While preparing product automata for union and subtraction of DFAs, I may have to mark state $F_1D_2$ as final, where $D_2$ is dead state in $DFA_2$ and $F_1$ is final state in $DFA_1$. State $F_1D_2$ need not be dead state in the union, subtraction and intersection DFA. Is that right?

3. I can also prepare union DFA by introducing new start state with $\epsilon$-transitions to start states of both $DFA_1$ and $DFA_2$. Then I can reduce the $\epsilon$-NFA if required. I will have to mark final state as explained in 1st bullet point in point 1. I found this approach is similar to product automaton approach, its just that it avoids unreachable states while product automaton approach forces to consider all, even unreachable states. Is that right?

4. If point 3 is correct, can I prepare intersection and subtraction DFAs by following approach stated in point 3 but marking final states as stated in point 1?

Answer 1

Yes, your understanding on point 2 is correct.

Your understanding on point 3 is mostly correct, except where you say "mark final state as explained in 1st bullet point in point 1". That statement doesn't type-check, as you can't do that to the $\epsilon$-NFA. If you've created an $\epsilon$-NFA, then its states are of the form $S_1$ or $S_2$ (where $S_1$ is a state of DFA1 and $S_2$ a state of DFA2), not of the form $S_1S_2$. So, it's not an option to mark $A_1F_2$ as final, as that's not a state of the $\epsilon$-NFA. Fortunately, you don't need to do that. You create the $\epsilon$-NFA as you described, then that works immediately with no further changes needed. The final states of the $\epsilon$-NFA are the final states of DFA1 and the final states of DFA2. (Perhaps you are thinking: create the $\epsilon$-NFA, convert it to a DFA using the subset construction, then mark final states specially. But there's no need to mark final states specially: the subset construction already takes care of marking the final states correctly.)

No, you can't do this for intersection or subtraction. Try it on some examples. I think you'll quickly be able to find some examples where it goes wrong. Also, my comments about point 3 apply here as well.