The star-height of a finite automaton and some related questions

Abstract

The paper is related to the star-height for nondeterministic finite automata, not for the star-height problem for regular languages. We describe an alternative proof of Kleene’s theorem, and then our version of the reduction of some problems related to the star-height to nondeterministic finite automata. For a given regular language, the corresponding finite automaton is constructed; the method we are considering has the property that the reverse construction gives the original regular expression. The publication of this not-so-complicated problem has two goals, the both are related to the future development of the topic under consideration. First, we assume the future development of the topic with the aim of describing a similar approach for generalized regular expressions. Secondly, another generalization is proposed, namely, consideration of the structures we describe for the so-called extended automata. Thus, the material of this article is necessary for the definition of extended generalized pseudo-automata, which the author proposes to cite in the next publication.