0
$\begingroup$

It seems to me that in order to construct the union and the product of two DFA we use basically the same method.

The difference is that when we make the accepting states for the resulting DFA. Suppose $A_{1}$ an DFA with $F_{1}$ as an accepting state, and $A_{2}$ an DFA with $F_{2}$ as an accepting state. In the case of an union of $A_{1}$ and $A_{2}$, the accepting states have either $F_{1}$ or $F_{2}$ or both, and in the case of a product, the accepted state is {$F_{1},F_{2}$}. Am I correct?

$\endgroup$
  • 1
    $\begingroup$ Could you clarify what you mean by "the union of two DFAs"? The usual way to show that there is a DFA accepting the language $L(A_1)\cup L(A_2)$ is to use the product of the DFAs. It's not clear to me that the union of two DFAs is well-defined or that it has any natural definition that gives a DFA rather than an NFA. $\endgroup$ – David Richerby Oct 24 '16 at 12:45
5
$\begingroup$

Please use the terminology correctly. The union operation is an operation defined on sets. It does not make sense to speak of the union of two automata.

The product construction can be used to give a constructive proof that the class of regular languages is closed under union. But with minor modifications, the product construction can also be used to show that the class of regular languages is closed under intersection as well as under set difference.

Assume that we have two DFA $M_1 = (Q_1,\delta_1,\Sigma,q^1_0,F_1)$ and $M_1 = (Q_2,\delta_2,\Sigma,q^2_0,F_2)$. In the case of intersection, define the set of accepting states as

$$F = \{ (q_1,q_2) \mid q_1 \in Q_1 \wedge q_2 \in Q_2 \} $$

For set difference, define the set of accepting states as

$$F = \{ (q_1,q_2) \mid q_1 \in Q_1 \wedge q_2 \notin Q_2 \} $$

$\endgroup$
  • $\begingroup$ Thank you for your answer. But one thing is still unclear to me. Suppose we have two languages: $L_{1}$ accepted by $A_{1}$ and $L_{2}$. How do I construct a DFA that accepts either $L_{1}$ or $L_{2}$ or both? $\endgroup$ – John Mayne Oct 24 '16 at 14:00
  • $\begingroup$ A DFA recognizes exactly one language, namely the set of strings that are accepted by it. It does not make sense to say that a DFA "accepts either $L_1$ or $L_2$ or both". Please use the terminology and the definitions correctly. $\endgroup$ – Hans Hüttel Oct 24 '16 at 14:03
  • 1
    $\begingroup$ @JohnMayne Yes you are on the correct track. What i could understand from your problem is you have two regular languages and now you need a DFA which accepts the language which corresponds to the union of the two regular language sets. The approach which you have adopted s correct except you need to be clear about the terminology. The method for union , intersection or set difference is essentially the same ; the difference is in determining the accepting states $\endgroup$ – Shubham Singh rawat Oct 24 '16 at 17:25
  • $\begingroup$ @ShubhamSinghrawat You made my doubts disappear. Thank you! $\endgroup$ – John Mayne Oct 24 '16 at 18:00

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.