Regular languages and minimal saturated automata.
Lill Kristiansen · NORA - Norwegian Open Research Archives · 1986
A saturated automaton relative to a regular language R is a non-deterministic automaton accepting R, and which contains homomorphic images of all automata accepting R.In this paper we construct a (unique) mini~al saturated automaton for a given regular language R and prove some basic properties.In particular, we show that the states in this automaton may be given a lattice structure, and that the states in the minimal deterministic automaton relative to R naturally gives a generator set for this lattice.And we describe how the homomorphisms from an arbitrary automaton accepting R into the minimal saturated automaton must behave.This is useful if one is interested in finding a state minimal nondeterministic automaton accepting R. It is also useful in giving lower bounds on the "star height" of R. The applications to the star height problem will not be treated here.(See [6]) ,1,. --,----------,--,~~ ---~---~_j_~-~-~