FSA supports the production of Prolog code on the basis of a finite automaton. Various tricks are employed to make the resulting code efficient (rather than readable), but functionality has an ever higher priority. The functionality is the same as that provided by the fsa_interpreter module, only faster. For pure speed, you should consider using the fsa_compiler_to_c module.
Depending on the type of automaton, the compilation provides the following Prolog predicate:
recognizer:
accepts(?String)
weighted recognizer:
w_accepts(+StringIn,?Weight)
transducer:
t_accepts(+StringIn,?StringOut)
weighted transducer:
wt_accepts(+StringIn,?StringOut,?Weight)
accepts/1 can be used to check a given string for acceptance by the automaton, or it can be used to generate all strings accepted by the automaton. Since input can be non-deterministic we check for epsilon-cycles by keeping track of a list of states visited after last consumption of input). There are cases where it would make more sense to pre-compute efree automata first. We provide it anyway.
t_accepts/2 can be used to transduce a given string or to produce pairs of strings, if the length of the input list is known. Since input can be non-deterministic we check for epsilon-cycles by keeping track of a list of states visited after last consumption of input). The predicate uses special meta-notation |N+| for `output' loops, to indicate that last N characters can be repeated any number of times. The compilation supports unknown symbols, including occurrences of delayed identity constraints (using a queue; trick due to Tamas Gaal was explained to me by Lauri Karttunen, Xerox Grenoble. Refer to Gerdemann and van Noord's paper in Grammars. Try: tminimize({[a:b,?,c],[a,?,d]}).
w_accepts/2 can be used to transduce a given string to the corresponding weight. In case of output loops only the minimum weight is produced. Since input can be non-deterministic we check for epsilon-cycles by keeping track of a list of states visited after last consumption of input.
wt_accepts/3 can be used to produce the transduction and weight for a given input string, or to generate triples of input, output and weight as long as the length of the input string is known.