4

How do we combine two dfa using intersection method ?

iva123
  • 3,395
  • 10
  • 47
  • 68
  • Is this homework? Otherwise, I am not familiar with the exact procedure spelled out in books, but I'm betting I could come up with a program to combine two DFAs that ran in time O(state transitions). – Omnifarious Jun 22 '10 at 19:41
  • I asked a [similar question](http://stackoverflow.com/questions/7732815/calculate-if-two-infinite-regex-solution-sets-dont-intersect) who's [answer](http://stackoverflow.com/a/7732923/188044) will probably work for this question. – Kendall Hopkins Dec 29 '11 at 19:41
  • Specifically, the part after the EDIT: spells out how to make a DFA accepting L1 intersect L2, given DFAs accepting L1 and L2. – Patrick87 Feb 04 '12 at 13:59

1 Answers1

2

Use the cross product construction, explained formally here.

Essentially you cross product the sets of states in each one to get a list of meta states corresponding to any combination of states for each machine. This allows you to do a parallel evaluation to accept if both accept.

Cannoliopsida
  • 3,044
  • 5
  • 36
  • 61