Finite-state Automata

A finite-state automaton is defined as a set of Prolog clauses. Some very limited familiarity with Prolog is assumed. A finite-state automaton is defined using the following relations:

start(State).

State is the start state. There should be at least one start state. Multiple start states are supported.

final(State).

State is a final state. There can be any number of final states.

trans(State0,Sym,State).

There is a transition from State0 to State with associated symbol Sym. There can be any number of transitions.

jump(State0,State).

There is an $\epsilon$-transition from State0 to State. There can be any number of jumps.

It is assumed that states and symbols are ground Prolog terms (but see the discussion on constraints in section 2.3 below). A finite-state automaton defining the language consisting of any number of a's over the alphabet {a,b} is defined as follows:

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

(1)

It is worthwhile to note that we do not require that the transition relation is total. In other words, there can be states that have no outgoing transitions for certain symbols. In such cases we assume that these transitions do exist, but lead to some non-final state from which you cannot leave. This state is sometimes called the sink. In example 1 state 1 is such a sink. Thus, we may abbreviate example 1 as

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

(2)

In the representation we are using, we do not require that the alphabet and the set of states is defined explicitly. If the previous example is further abbreviated as:

start(0). final(0). trans(0,a,0).

(3)

the information that b is part of the alphabet is lost. This is problematic if the complement of this language is to be constructed; for this reason the difference operation has been introduced (cf. section 4.2).