0
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Do you know how to turn an NDFA into a DFA? $\endgroup$ – Theodore Norvell Feb 24 '14 at 20:34
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Union_of_two_regular_languages $\endgroup$ – D.W. Feb 24 '14 at 22:24
  • 1
    $\begingroup$ As well as being on Wikipedia, this proof is in any textbook on automata theory. $\endgroup$ – David Richerby Feb 24 '14 at 22:37
  • $\begingroup$ 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. $\endgroup$ – slallum Feb 25 '14 at 6:24
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Feb 26 '14 at 6:35
4
$\begingroup$

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$.

Intuitively, this works by demonstrating that we can model two DFAs executing in lockstep using the DFA formalism itself; two DFAs executing in lockstep is equivalent to the DFA constructed above. We have chosen to accept a string if either of the machines accepts, but as you can see, we could define a DFA for any of the standard binary set operations: union, intersection, difference, symmetric difference, etc.

$\endgroup$
  • $\begingroup$ Thanks a lot for the answer. I have a related question: what is the difference between F3 that you defined and F1XF2? $\endgroup$ – slallum Feb 25 '14 at 6:20
  • 1
    $\begingroup$ @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$). $\endgroup$ – Patrick87 Feb 25 '14 at 16:59
  • $\begingroup$ That clarifies everything! Thank you so much :) $\endgroup$ – slallum Feb 26 '14 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.