Some examples

The FSA Utilities are available through a single UNIX command fsa which can take a number of different options. Suppose we have defined the following finite-state automaton, defining the language consisting of all the strings made up of an even number of a's followed by an even number of b's, in a file called aabb.nd:

start(0). trans(0,a,1). trans(1,a,0). jump(0,2). trans(2,b,3). trans(3,b,2). final(2).

(5)

In order to determinize this automaton, we give the following UNIX command (note that in these examples lines starting with a % are typed to the UNIX shell; the lines that follow are output of the FSA Utilities program):

% fsa -d <aabb.nd >aabb.d

(6)

This command writes the determinized automaton to the file aabb.d. This file now contains:

start(q0). final(q0). final(q1). trans(q0,b,q2). trans(q0,a,q3). trans(q2,b,q1). trans(q1,b,q2). trans(q3,a,q0).

(7)

It is also possible to create an automaton on the basis of a regular expression. The file aabb.d could also be obtained by the command:

fsa -r '(a.a)* .(b.b)*' | fsa -d > aabb.d

(8)

In such regular expressions the dot (.) is used to indicate concatenation, union is defined by the semi-colon (;) and Kleene closure is defined by the asterisk (*).

A minimized automaton is obtained with the -m option. We can, for example, pipe the result of determinization to another incarnation of the fsa command. The following pipe produces the minimal finite-state acceptor for the language consisting of an even number of a's followed by an uneven number of b's:

% fsa -r '(a.a)* .(b.b)* .b' | fsa -d | fsa -m start(q0). final(q1). trans(q0,a,q2). trans(q0,b,q1). trans(q1,b,q3). trans(q2,a,q0). trans(q3,b,q1).

(9)

Next consider a finite-state transducer which copies its input (strings of a's and b's) to its output, except that if an a is followed by a b, then this a becomes a b. Suppose this transducer is defined in the file a2b.tnd as follows:

start(0). trans(0,b/b,0). trans(0,a/b,1). trans(1,b/b,0). trans(0,a/a,2). trans(2,a/b,1). trans(2,a/a,2). final(0). final(2).

(10)

Such a transducer can be determinized (using the algorithm described in Roche and Schabes ([12]) with the command:

% fsa -td <a2b.tnd >a2b.td

(11)

The file a2b.td now contains:

start(q0). final_td(q0,[]). final_td(q1,[a]). trans(q0,b/b,q0). trans(q0,a/'$E',q1). trans(q1,b/b,q2). trans(q2,'$E'/b,q0). trans(q1,a/a,q1).

(12)

In order to use this transducer to transduce strings, it may be worthwhile to compile it into an efficient Prolog program implementing the transduction. The Prolog program will be fully deterministic; using first argument indexing, this determinism is visible to modern Prolog compilers. This implies that transduction is computed in linear time (with respect to the size of the input), and is independent of the size of the transducer.

% fsa -ct <a2b.td >a2b.pl

(13)

The file a2b.pl contains:

t_accepts(S,T) :- t_accepts_q0(S,T). t_accepts_q0([],[]). t_accepts_q1([],[a]). t_accepts_q0([S|T],O) :- t_accepts_q0(S,T,O). t_accepts_q1([S|T],O) :- t_accepts_q1(S,T,O). t_accepts_q2([S|T],O) :- t_accepts_q2(S,T,O). t_accepts_q0(b,T,[b|O]) :- t_accepts_q0(T,O). t_accepts_q0(a,T,O) :- t_accepts_q1(T,O). t_accepts_q1(b,T,[b|O]) :- t_accepts_q2(T,O). t_accepts_q1(a,T,[a|O]) :- t_accepts_q1(T,O). t_accepts_q2(S,[b|O]) :- t_accepts_q0(S,O).

(14)

This Prolog program can be used to transduce the string aabbc by issuing the command:

% fsa -transduce a a b b < a2b.pl a b b b

(15)

In regular expressions it is possible to use pairs of symbols in order to obtain finite-state transducers. Thus we can have examples such as the following:

% fsa -r '((a:a;b:b;c:c)* .(d:e)* .(a:a;b:b;c:c)*)*' \ | fsa -td start(q0). final_td(q0,[]). trans(q0,d/e,q0). trans(q0,c/c,q0). trans(q0,b/b,q0). trans(q0,a/a,q0).

(16)

As another example, it is possible to compose aabb.nd with the transducer a2b.tnd. The following pipe produces the minimized, determinized composition:

fsa -compose_fsa aabb.nd a2b.tnd | fsa -d \ | fsa -m > result.d

(17)

Such automata can be inspected with the Tk Widget (presented in section 5), for example, as in figure 3.

In this paper the use of the FSA Utilities toolbox is illustrated by means of UNIX commands. However, this is not the only possible way of using the toolbox. Care has been taken to implement the toolbox in such a way that it is straightforward to use each of the operations as a Prolog library. For this reason most of the operations are defined in separate modules.