contents index next

1. FSA6: Finite State Automata Utilities Version 6

(manual generated with FSA Utilities version 6.159)

FSA6 is a collection of utilities to

1.1 Functionality

1.1.1 Constructing Finite Automata with Regular Expressions

Many basic regular expression operators are provided, both for acceptors and transducers. Moreover, it is easy to define new regular expression operators. The built-in regular expression operators include:

1.1.2 Manipulating Finite Automata

Tools are provided to manipulate finite automata. Such manipulations include determinization and minimization (both the classical algorithms for recognizers and the recent algorithms for transducers are provided).

1.1.3 Applying Finite Automata

1.1.4 Visualizing Finite Automata

Much attention has been paid to be able to visualize finite state recognizers and finite state transducers. Support includes built- in visualization and interfaces to third party software:

1.2 How to use the toolbox

There are a number of ways that the toolbox is meant to be used:

% fsa -tk
% fsa write=postscript -r '[a,b+,c*,d]' | ghostview -
% sicstus
SICStus ...
Licensed to ...
| ?- use_module(fsa_library).
...
...
...
yes
| ?- fsa_regex_atom_compile('[a*,b^,{d,e}]',L).
L = fa(r(fsa_preds),3,[0],[1],[trans(0,a,0),trans(0,b,2),
    trans(0,d,1),trans(0,e,1),trans(2,d,1),trans(2,e,1)],[]) ?
yes
| ?- fsa_regex_transduces('{a:b,? -a}*',"ababac",L), atom_codes(Atom,L).
L = [98,98,98,98,98,99],
Atom = bbbbbc ?
yes
| ?-

All predicates that are imported have names starting with *fsa*. All module names start with fsa as well.

1.3 Examples

The package comes with a number of larger examples These examples include both automata and extended regular expression definitions.

1.5 References

1.6 Papers using FSA

1.7 Links

1.8 Copyright

Copyright c 1995 - 1999 by Gertjan van Noord. This program is distributed under Gnu General Public License (cf. the file COPYING in distribution).

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

1.9 Acknowledgements

Helpful suggestions, feedback, etc., from a variety of people, too many to list here. Gosse Bouma and Dale Gerdemann were exceptionally influential.

1.10 Author

Gertjan van Noord, mailto:vannoord@let.rug.nl

contents index next