1
$\begingroup$

Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the combination of those states to the new automata and so on. So that I do not have to first take every possible combination of states and then fill the transitions and finally remove the inaccessible ones. Is this "faster way" correct?

$\endgroup$

2 Answers 2

2
$\begingroup$

Yes, this works, as long as you do it right. If you do it right, you only explore the reachable states of the product automaton. Since the other states aren't reachable, it doesn't matter whether you include them in the resulting automaton or not.

$\endgroup$
0
$\begingroup$

That's basically the idea. It's effectively equivalent to the standard algorithm:

  1. Construct an NFA with all the states and transitions of the DFAs being combined, plus a new state $q_0$ with has ε transitions to each start state of the DFAs. The set of final states of the NFA is the union of the final states of the DFAs, and the start state of the NFA is $q_0$.

  2. Use the subset construction to create a new DFA from the NFA.

In fact, the above algorithm would combine NFAs as well.

$\endgroup$
3
  • $\begingroup$ Thank you. Isn’t there always only one initial state in the resulting automata which is the combination of all initial states of the DFAs/NFAs? So a lambda transition to the initial states is not needed since we only have one? $\endgroup$
    – Ronald
    Aug 24, 2022 at 6:15
  • $\begingroup$ @Ronald: you can't use an initial state of a DFA if that state has a transition back to itself. Creating the new state with lambda transitions keeps you out of trouble; if it's not needed, the subset construction will soon get rid of it. But there's no guarantee that's the case, so it's easier to just create the new start state and then let the subset construction do its thing. $\endgroup$
    – rici
    Aug 24, 2022 at 6:49
  • $\begingroup$ thank you. Why can’t I use an initial state if it has a transition to itself? And in your answer you say “each start state”, by that you mean each subset of the resulting automata where there is a start state of one of the automata? $\endgroup$
    – Ronald
    Aug 24, 2022 at 17:35

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.