CODEWITHSUNDEEP
intersectionfinite-automatadfanfa
Antonio Santoro
Antonio Santoro

Reputation: 907

Is it possible to compute the intersection of two non completely specified DFA?

If the two DFAs for which the intersection has to be computed are not completely specified, it can happens that it is possible to reach a state containing only one state of the two DFAs. Is that correct or additional steps are required before proceeding to the computation of the intersection?

Upvotes: 0

Views: 444

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Given a DFA that's missing a transition on some state, you can always convert that into a "full" DFA by adding in a new state qdead that isn't accepting and has transitions only to itself, then adding transitions into qdead for each missing transition. So in that sense, if you don't have full DFAs specified, you could always convert the DFAs into "full" DFAs and then run the cross-product construction as usual.

If you're specifically building a DFA For the intersection of the two input DFAs, though, you don't need to do this because all states generated this way are going to be equivalent to one another (none of them can reach an accepting state in the original machine). There are a couple of ways of forming intersections, and depending on which approach you take you could make anywhere from minor to major adjustments:

  • One algorithm simply computes all possible pairs of states from the two input DFAs and then fills in the transitions by looking at where the pairs of states transition to. If you're using this approach, you can just have each state that's missing a transition in one of the input DFAs have no transitions in the cross-product, simulating "one of the automata would have died here."
  • Another algorithm uses a DFS or BFS to only construct reachable states in the cross-product. In that case, no modifications are necessary - if you find a pair of states where one is missing a transition, simply don't add any successor states.

On the other hand, if you're doing something like a union construction, where you only need one of the two states to be accepting, these approaches won't work because you need to be able to simulate the idea of "one automaton died, and the other is still happily running." For that, adding in the explicit dead state is a simple and effective approach.

Upvotes: 1

Related Questions