# Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's. How can I construct a new DFA for the regular language $L1 \cup L2$?

• Do you know how to turn an NDFA into a DFA? – Theodore Norvell Feb 24 '14 at 20:34
• en.wikipedia.org/wiki/Union_of_two_regular_languages – D.W. Feb 24 '14 at 22:24
• As well as being on Wikipedia, this proof is in any textbook on automata theory. – David Richerby Feb 24 '14 at 22:37
• I do know the wikipedia article and I checked it out, and I also know how to turn NDFA into a DFA. But still - I think that the constructed DFA I'll make out of the NDFA (that's constructed according to the wikipedia article) will be different from the more readable answer here. And I did search for the answer on the internet, and didn't find any that contains DFA and not NDFA. – slallum Feb 25 '14 at 6:24
• slallum, we expect you to do research before asking here and to show us what you've tried in the question. If you knew about the Wikipedia article, it would have been better to mention it in your question and explain in what sense it fell short of what you were looking for. The first rule of asking others for help is to respect their time. – D.W. Feb 26 '14 at 6:35

Let's denote the sets of states in $A_1$ and $A_2$ by $Q_1$ and $Q_2$, respectively. Furthermore, let's denote by $F_1$ and $F_2$ the accepting states of these machines, $q_0'$ and $q_0''$ the start states of these machines, and $\delta_1$ and $\delta_2$ the transition functions of these machines.
We can use the Cartesian-product-machine construction to define an automaton $A_3$ which accepts $L(A_1) \cup L(A_2)$ as follows. First, let $Q_3 = Q_1 \times Q_2$ be the set of states. Now, define $F_3 = \{(q_1, q_2) \in Q_3 \mid q_1 \in F_1 \vee q_2 \in F_2\}$. Let $q_0'''$ be the start state and define $\delta_3((q_1, q_2), \sigma) = (\delta_1(q_1, \sigma), \delta_2(q_2, \sigma))$.
Consider the functioning of such a machine. By virtue of its being in some state $(q_1, q_2) \in Q_3$, we know by construction that $A_1$ would have be in state $q_1$ after seeing the same input, and we know $A_2$ would be in stare $q_2$ after seeing the same input. $A_3$ will accept if either $q_1$ was accepting in $A_1$ or $q_2$ was accepting in $A_2$, because of how we defined $F_3$.
• @slallum $F_1 \times F_2$ only contains states in which both components represent accepting states in their respective automata. I define $F_3$ so that it contains states such that at least one component is accepting in its respective automaton; in other words, $F_1 \times F_2 \subseteq F_3$ (with equality only if $F_1 = Q_1 \wedge F_2 = Q_2$). – Patrick87 Feb 25 '14 at 16:59