1
$\begingroup$

How would you modify the Product Construction for DFAs to find a DFA that recognises the union of two regular languages with different alphabets. I am not looking for a way of finding an NFA then converting that to an equivalent DFA but explicitly modifying the Product Construction Theorem.

$\endgroup$

1 Answer 1

2
$\begingroup$

We can adapt the product construction, but we can also change the original DFA $A_1$ over alphabet $\Sigma_1$ into a new DFA $A$ accepting the same language, but over a larger alphabet $\Sigma\supseteq \Sigma_1$.

Just add a new dummy state $d$ and add transitions to $d$ from every state, for every extra letter $\sigma\in \Sigma\setminus \Sigma_1$. From $d$ we have a loop back to $d$ for all letters.

Now we can perform the product construction to two (deterministic) automata with the same alphabets. Alternatively we start with the original automata, and for every letter that is not defined for both automata we move that component to dummy state $d$, and we stay in that state. The effect is the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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