next up previous contents
Next: Epsilon-free FSM's Up: Finite State Machines Previous: Finite State Machines

Intersection of FSM's

Given two FSM's, one can ask the question as to whether there is a string that both machines accept, that is, whether the intersection of the languages accepted by the two machines is non-empty.

This turns to be possible, and not very difficult. As a matter of fact, we've already essentially written a program that does this. You might have noticed that our representations of strings and machines are actually very similar. In fact, a string can be understood as a FSM, simply by viewing the string/4 predicate as a machine transition predicate. In this case the string's states are integers, the initial state is 0 and the final state is the string length. Viewed this way, a string is simply a FSM that recognizes exactly that one string.

Viewed in this way, the verb|accept/2| predicate above, which we wrote as determining whether a FSM accepts a string, can be trivially modified to determine whether two machines accept languages with a non-empty intersection. We leave it to the reader to modify the definition of accept/2 to check intersection, and to test it with several examples.


next up previous contents
Next: Epsilon-free FSM's Up: Finite State Machines Previous: Finite State Machines
David S. Warren
1999-07-31