3.3.5 Intersection

Continuation.

We now turn to the more interesting operations of union and intersection. We implement them simply by giving additional clauses for start/2, trans/2 and final/2. Let's look at an example call to see how this works. We assume that our database contains two automata named a1 and a2 (accepting and , respectively). As said above we call

scan(cp((a1,a2),b2)).

to build an automaton for and save it as b1.

Just as when we were simply copying a1, the first substantial thing to happen is a call to start/2, like this:

start(cp((a1,a2),b2),S)

Again, this leads to another call to . But this time, this call will not directly match a start state specification of any of the automata in the database. Rather it will look like this:

start((a1,a2),S)

The first argument contains our intersection symbol, the operator ``,''. And we provide the following clause of start/2 to match in this case:

start((A1,A2),S1/S2):-
  start(A1,S1),
  start(A2,S2).

This clause produces the start state of our intersection automaton. The start state has to be the pair of the start states of a1 and a2 according to the construction method discussed in Section 3.2.2. We represent this in Prolog using the /-operator.

Next, control returns to the embedding call start(cp((a1,a2),b2),S), and the start state of the new b1 is asserted to the database.

Similarly, the calls to trans/4 issued in scan_state/2 now lead to one further call, which processes the intersection operator. Here's how we implement trans/4 for intersection:

trans((A1,A2),S1/S2,D1/D2,X):-
  trans(A1,S1,D1,X),
  trans(A2,S2,D2,X).

This code translates our ideas from Section 3.2.2: If a transition over some symbol is present in A1 and A2, the intersection-automaton should contain a transition over that symbol between the corresponding pair-states. The above code ``builds'' this transition. It is then asserted when control passes back to the embedding call that performs the cp-operation.

The third predicate that has to be extended is final/2 (called by check_final/2 in scan_state/2). Here is the clause we will add:

final((A1,A2),S1/S2):-
  final(A1,S1),
  final(A2,S2).

Any pair of final states of A1 and A2 is a final state of the intersection automaton. Again, the new final states are asserted by the embedding final/2-call processing the cp-instruction.