Finite-state Acceptors

The -accepts Words option can be used to check whether a given string of symbols (Words) is accepted by a given finite state automaton (read from standard input). This automaton is defined according to the conventions discussed in section 2. Alternatively this file is a compiled finite-state automaton as produced by the -compile option presented below. The program determines whether Words is accepted by this automaton or not. If it is, the program returns successfully; otherwise it exits with exit code 1. Note that this procedure is only guaranteed to be linear in the length of the input string if the finite state automaton is both deterministic and compiled. In the case of such a compiled deterministic automaton SICStus Prolog's first argument indexing is exploited to ensure that acceptance is also independent of the size of the automaton.

The -produce option is used to generate all possible strings accepted by the input automaton. Strings are produced in increasing length. Clearly this operation need not terminate if the automaton defines a language consisting of an unbounded number of strings.

Consider the following examples.

% fsa -a a a a a b b < aabb.nd yes % fsa -a a a a b b < aabb.nd no % fsa -d <aabb.nd | fsa -c > aabb.pl % fsa -a a a a a b b b b b b < aabb.pl yes

(18)

% fsa -p <aabb.nd a a b b a a a a a a b b b b b b a a a a a a a a a a b b a a b b b b b b b b b b ...

(19)