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. We only note that in a Kleenean algebra

The most familiar Kleenean algebra is the algebra of regular languages over a given finite alphabet. They actually form 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.

A finite automaton M = (Q,I,Tr,F), consisting of a finite set Q of `states', subsets I of initial and F of final states, and a family Tr of binary transition relations on Q, labelled by letters of the alphabet, accepts the regular language L(M) consisting of all sequences of letters labelling paths in M from initial to final states. But this is only the special case of a finite automaton over the algebra of regular languages.

More generally, a finite automaton M = (I,T,F) over a Kleenean algebra K, is a linear transformation T : K^n -> K^n on some n-fold cartesian power of K, together with two 0-1-vectors of length n; it defines the element L(M) = I';T*;F of K, where I' is the transposition of I. The translation T can be represented by a square matrix of dimension n over K.

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.


Last Modified: March 7th, 2000
Please send bug reports and comments to Hans Leiß, Universität München, CIS.