3.3.1 The scan-Predicate

All operations on FSAs are carried out within one general framework.

All operations on FSAs that we are going to implement will be carried out within one general framework: We will define a predicate scan/1. This predicate takes as input a symbolic specification of the operation to be performed. Then it traverses the FSA(s) referred to in its input and calls helper predicates according to the operation that has been requested. We will use the Prolog operators ; and , to specify union and intersection in the input to scan/1. But how can we refer to the FSAs ot be operated on? Recall that our Prolog notation (see Section 1.4) requires us to give a name to each FSA that we put in the database (the first argument of the clauses that make up the automaton). And it is these names that we use in the operation specifications for the scan/1-predicate.

Here are two examples. Let's assume our database contains two automata named a1 and a2 (accepting and , respectively). Then the specification used to request the union-automaton (for ) will be:

a1;a2

To specify an automaton for we write:

a1,a2

As indicated, our scan/1-predicate will have only one argument. Now if this single argument is to be filled by the specification of the operation to be performed, there's no argument left for output. Of course we don't want to lose the automaton resulting from performing the requested operations. But we won't use an additional argument for output. Instead, we will implement an operation cp that saves an automaton under a new name. For instance calling

scan(cp(a1,b1)).

results in the automaton a1 being copied to an automaton b1. If for instance a1 is our first ``laughing machine'' from Section 1.4.1, we will have the following additional database entries after running scan(cp(a1,b1)).:

start(a1,1).

final(a1,4).

trans(a1,1,2,h).

trans(a1,2,3,a).

trans(a1,3,4,!).

trans(a1,3,2,h).

The cp-operation is used to save the output of other operations. For instance to intersect a1 and a2 and save the result as b2, we call:

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