[Solved]: Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Problem Detail: 

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

Asked By : slallum

Answered By : Patrick87

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22000

 Ask a Question

 Download Related Notes/Documents