patternMinor
Finding the union, subtraction, and intersection of two DFAs
Viewed 0 times
theunionsubtractionintersectiontwodfasfindingand
Problem
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:
-
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 DFA1 and DFA2 respectively and $F_1$ and $F_2$ are final states of DFA1 and DFA2 respectively, then,
$A_1F_2, F_1A_2$ and $F_1F_2$.
$F_1F_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?
-
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?
-
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?
-
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 DFA1 and DFA2 respectively and $F_1$ and $F_2$ are final states of DFA1 and DFA2 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 DFA1-DFA2, state having DFA1's final state but non final state of DFA2 will be final: $F_1A_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?
-
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?
-
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#119395, answer score: 2
Revisions (0)
No revisions yet.