next up previous
Next: Some examples Up: Representation Previous: Finite-state Transducers

Simple Prolog Constraints

Because finite-state automata are defined by Prolog clauses, it is very simple to attach Prolog constraints. For example, suppose that for a certain application it is useful to consider two subclasses of the alphabet, namely V (vowels) and C (consonants), we could then use the following technique to define the sequences C*V*C*:

vowel(a).   vowel(e).   vowel(i).   vowel(o).   vowel(u).

cons(b).    cons(c).    cons(d).    cons(f).    cons(g).
cons(h).    cons(j).    cons(k).    cons(l).    cons(m).
cons(n).    cons(p).    cons(q).    cons(r).    cons(s).
cons(t).    cons(v).    cons(w).    cons(y).    cons(z).

start(0).   final(2).   jump(0,1).  jump(1,2).
trans(0,C,0) :- cons(C).
trans(1,V,1) :- vowel(V).
trans(2,C,2) :- cons(C).

I only allow constraints for which Prolog's built-in search procedure terminates. These Prolog constraints therefore do not increase the formal power of the formalism, although they are useful to define automata in a convenient and concise way.

Noord G.J.M. van