Finite State Machines

We represent a finite state machine using three relations:

1.

m(MachineName,State,Symbol,TargetState) which describes the transition relation for a machine, with MachineName being the name of the machine (to allow us to represent many machines using the same relation), State is a state of the FSM, Symbol is an input symbol, and TargetState is a state to which the machine transitions from State on seeing Symbol.

2.

mis(MachineName,InitialState) where InitialState is the initial state of the FSM named MachineName.

3.

mfs(MachineName,FinalState) where FinalState is a final state of the FSM named MachineName.

By including a MachineName in each tuple, we can use these relations to represent a number of different FSM's. This will be convenient later.

We will use the symbol '' (the atom with the empty name) as a pseudo-symbol to represent epsilon transitions, transitions a machine can make without consuming any input symbol.

For example, the following relations represent the machine pictured in Figure 5.1, which we will call m0s1s2s, since it recognizes strings made up of a string of 0's followed by a string of 1's followed by a string of 2's:

m(m0s1s2s,q0,0,q0).
m(m0s1s2s,q0,'',q1).
m(m0s1s2s,q1,1,q1).
m(m0s1s2s,q1,'',q2).
m(m0s1s2s,q2,2,q2).

mis(m0s1s2s,q0).

mfs(m0s1s2s,q2).

  

Figure 5.1: The finite state machine: m0s1s2s

We represent strings with two relations. Again we will name strings for convenience.

1.

string(StringName,Index,Symbol,Index1) where StringName is the name of the string, Symbol is the Index1-th symbol in the string and Index is Index1-1. For example, the string ``001112'', which we will call s1, would be represented by:

string(s1,0,0,1).
string(s1,1,0,2).
string(s1,2,1,3).
string(s1,3,1,4).
string(s1,4,1,5).
string(s1,5,2,6).

and string ``021'', which we'll name s2, would be represented by:

string(s2,0,0,1).
string(s2,1,2,2).
string(s2,2,1,3).

2.

stringlen(StringName,Length) where Length is the length of the string named StringName. For example, for the previous examples, we would have the facts:

stringlen(s1,6).
stringlen(s2,3).

A FSM is said to accept a string if it executes in the following way: it starts in the initial state, and makes a transition to the next state along a path labeled by the symbol it is looking at. It consumes that symbol and then makes another transition based on the next symbol in the string. It continues in this way until all symbols are consumed, and if the machine is then in a final state, the string is accepted; otherwise it is rejected. If there is an epsilon-transition from one state to another, the machine can make such a transition without consuming a symbol of the input.

Now we can easily write a specification in XSB that defines when a machine accepts a string, as follows:

:- auto_table.

% A machine accepts a string if the machine starts in the initial state,
%    recognizes the string, ending in a final state and has consumed the
%    entire string.
accept(MachineName,StringName) :- mis(MachineName,StateStart),
        recognize(MachineName,StringName,StateStart,StateFinal,0,StringFinal),
        mfs(MachineName,StateFinal),
        stringlen(StringName,StringFinal).

% recognize(MachineName,StringName,MState0,MState,SLoc0,SLoc) is true
% if machine MachineName started in state MState0 can transition to
% state MState by recognizing the substring from location SLoc0 to SLoc
% of the string named StringName.

% The empty input string
recognize(_,_,MState,MState,SLoc,SLoc).
% regular transitions
recognize(MachineName,StringName,MState0,MState,SLoc0,SLoc) :-
        string(StringName,SLoc0,Symbol,SLoc1),
        m(MachineName,MState0,Symbol,MState1),
        recognize(MachineName,StringName,MState1,MState,SLoc1,SLoc).
% Epsilon transitions
recognize(MachineName,StringName,MState0,MState,SLoc0,SLoc) :-
        m(MachineName,MState0,'',MState1),
        recognize(MachineName,StringName,MState1,MState,SLoc0,SLoc).

The definition of accept says that a machine accepts a string if StateStart is the initial state of the indicated machine, and the machine transits from StateStart to StateFinal while recognizing the string starting from 0 and ending at StringFinal, and StateFinal is a final state of the machine, and StringFinal is the length of the string.

The definition of recognize/6 describes how a machine moves through its states while recognizing (or generating) a sequence of symbols. The first clause says that for any machine and any string, when the machine stays in the same state, no symbols of the string are processed. The second clause says that a machine moves from MState0 to MState recognizing a substring if the next symbol in the substring is Symbol, and there is a transition of the current machine on that Symbol that takes the machine from MState0 to MState1, and the machine recognizes the rest of the substring from that state MState1 getting to MState. The third clause handles epsilon transitions; it says that a machine moves from MState0 to MState recognizing a substring if there is an epsilon transition from MState0 to a MState1 and the machine recognizes the entire string from MState1 to MState.

For example, accept(m0s1s2s,s1) succeeds, but accept(m0s1s2s,s2) fails:

warren% xsb
XSB Version 1.6.0 (96/6/15)
[sequential, single word, optimal mode]
| ?- [automata].
[automata loaded]

yes
| ?- accept(m0s1s2s,s1).
++Warning: Removing incomplete tables...

yes
| ?- accept(m0s1s2s,s2).

no
| ?-

This is a right-recursive definition of recognize/6, so it might seem that this should not need tabling. And indeed for this particular machine and string, Prolog would evaluate this definition just fine. However, there are machines for which tabling is required. Can you give an example of such a machine?

Also, it is possible to give this specification in a left-recursive manner. That is also an exercise for the reader.