I'm currently looking at deterministic finite automata, and learning how to combine two DFAs using AND or OR. I think I understand how to construct the INTERSECTION (AND) of two DFAs, but I'm at a loss when it comes to constructing the UNION (OR) of the same DFAs.
For instance, assume we have language L defined as follows:
L = {w | w contains the substring ab (AND/OR) ba}This can be thought of as two sub-languages, respectively:
L1 = {w | w contains the substring ab}
L2 = {w | w contains the substring ba} As such, we can construct DFAs for each language (namely L1 and L2), and combine them using either the AND og OR scheme.
AND - Intersection
For intersection (AND), the individual DFAs become as follows:
Furthermore, the intersection M = M(L1) AND M(L2), corresponding to the language
L = {w | w contains the substring ab AND ba}would be represented by the following DFA:
This should, after what I gather, be correct. If not; please tell me where the faults are.
QUESTION
However, HOW does one construct the UNION of the same DFAs?
I have seen some examples/solutions online, such as the figure below, but I do not understand how they have reached this setup.
Any help on this is extremely appreciated!
$\endgroup$4 Answers
$\begingroup$The construction of DFAs via (left) derivatives seems not to be as commonly known as it should be; see this paper.
The left derivative of a language $L$ over an alphabet $\Sigma$, with respect to a symbol $a$, is $$D(L,a) = \{w\in\Sigma^*\mid aw\in L\}.$$ For a regex $r$, let $L$ be the language described by $r$; then $D(r,a)$ is a regex matching $D(L,a)$; one can be computed easily.
The states of your DFA are regexes; a regex $R$ transitions to $D(R,a)$ under symbol $a$. The initial state is the given regex, and the accept states are those regexes which match the empty string $\epsilon$. It's convenient to define derivatives with respect to strings via $D(L,aw)=D(D(L,a),w)$.
For the regex $R=\texttt{/.*(ab|ba).*/}$, we get the following: $$\begin{array}{c|c} w& D(R,w)\\ \hline \epsilon& R\\ a & R|\texttt{/b.*/}\\ b & R|\texttt{/a.*/}\\ ab & \texttt{/.*/}\\ ba & \texttt{/.*/}\\ \end{array}$$ As $D(\texttt{/.*/},s)=\texttt{/.*/}$ for any symbol $s$, no further states are created, so this results in a 4-state DFA for $R$, with one accept state corresponding to the language $\texttt{/.*/}$, the only state whose language contains $\epsilon$. This agrees with the picture you provided.
$\endgroup$ $\begingroup$If your definition of DFA allows for multiple accept states (usually it does), then the simplest way is to take the same DFA for the intersection, with the only difference being that your set of accept states should contain any state in which either machine 1 was accepting or machine 2 was accepting. In this case, that means any state with either a "3" or a "C" in the name.
This will not result in a DFA that looks identical to the one you posted, but it will result in a different DFA that accepts the union of the two languages.
You can think about which states your diagram really needs: some of them may not be reachable from the start state, so perhaps you can eliminate them, and perhaps you can combine some other states in such a way that you will end up getting something that looks like the one you posted. But if your only goal is to find any DFA that will accept that language, the construction for the intersection and the construction for the union can be the same, with only the set of accepting states differing.
$\endgroup$ $\begingroup$Hint. if you know how to handle the complement, you can use the formula $K \cup L = (K^c \cap L^c)^c$, where $L^c$ denotes the complement of $L$.
$\endgroup$ $\begingroup$AND- Intersection,therefore we use cross products.
OR - Union - for the union of two $2$ DFA's we need to combine them in such a way that both of their starting states are merged. Then you get the required DFA, which may not be minimal.
$\endgroup$
