A Finite Automata Library for Standard ML

Introduction to the Automata Library This Automata Library collects modules dealing with computations in Kleenean algebras KA = (K,+,;,*,0,1), possibly with some constants for elements of K. The most familiar Kleenean algebra is the algebra of regular languages over a given finite alphabet. It is the free Kleenean algebra over the alphabet, but there are other interesting interpretations as well, like the algebra of binary relations over a set, where ; is relational composition and * the transitive closure.

Source code


Roughly, the library contains programs to

In more detail, this library provides

The Library also has an implementation of finite automata extended by a counter, which can be used to generate pattern matchers for regular pattern search:

The Library also provides some (preliminary and incomplete) treatment of systems of regular recursion equations, or EBNF-grammars, i.e. grammars in extended Backus-Naur-form. In particular, it contains This package was written to support teaching of finite automata and formal languages. Efficiency was not a main interest, but the minimization algorithm is O(n*log(n)) if the set of final states is O(log(n)); hashing the final states would make it O(n*log(n)) in general.


Please send bug-reports and comments to: Hans Leiß.
Last Modified: March 9th, 2000, January 22th, 2010