1.4.1 Representing FSAs in Prolog
Representing FSAs in Prolog.
In our implementation, we are going to treat FSAs as passive data structures that are manipulated by other programs. In a way, the very first pictures of FSAs in this chapter showed a similar division into a declarative part and a procedural part: the network-like graph is a declarative representation of the FSA and the ``egg'' is the program. Depending on what instructions we give to the ``egg'', we can use it to generate words (as in the picture) or to recognize words using the same FSA.
Separating declarative and procedural information is often a good idea. In many cases, it makes it easier to understand what is going on in a program, to maintain a program, and to reuse information. In the chapter on Context Free Grammars (Chapter 5), we will learn more about why the machine oriented view is unattractive.
We will use three predicates to represent FSAs:
start/2final/2trans/4
The first argument in each of these predicates is simply an atom naming the automaton to be specified. Let's start by specifying our first laughing machine, and call it a1. It will have the following Prolog representation:
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).
start(a1,1), for instance, says that 1 is the initial state of a1; and final(a1,4) says that 4 is its final state (to be precise: one final of its states. But incidentally, a1 has only one final state). And trans(a1,1,2,h) says that there is a h-transition from state 1 to state 2 in a1.
We will, furthermore, use the atom '#' to mark jump arcs. Here is the laughing machine with the jump arc. We shall give it the name a2:
start(a2,1).
final(a2,4).
trans(a2,1,2,h).
trans(a2,2,3,a).
trans(a2,3,4,!).
trans(a2,3,1,'#').
And here's the non-deterministic version (under the name a3):
start(a3,1).
final(a3,4).
trans(a3,1,2,h).
trans(a3,2,3,a).
trans(a3,3,4,!).
trans(a3,2,1,a).
As you can see, the Prolog representation of these finite state machines is a straightforward translation of the graphs that we have been drawing in the previous sections.