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

Boris Melnikov


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. 

Full Text:



Melnikov B. Ob odnoy klassifikacii ... [On a classification of sequentional context-free languages and grammars]. Vestnik of Moscow University. Series 15: Computational Mathematics and Cybernetics. 1993, no. 3, pp. 64-69. (in Russian)

Melnikov B. and Vakhitova A. Some more on the finite automata. The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 1998, vol. 5, no. 3. pp. 495-506.

Melnikov B. O zvyozdnoy vysote regulyarnogo yazyka ... [On the star-height of a regular language. Part III: The star-height of an automaton and the scheme of the transformation algorithm]. Heuristic algorithms and distributed computations. 2014, no. 3, pp. 60-76. (in Russian)(

Eggan L. Transitions graphs and the star height of regular events. Michigan Mathematical Journal. 1963, vol. 10, pp. 385-397.

Hashiguchi K. Algorithms for determining relative star height and star height. Information and Computation. 1988, vol. 78, pp. 124-169.

Perrin D. Finite Automata. Handbook of theoretical computer science, Vol. A. MIT Press Cambridge, MA, USA, 1990, 57 p.

Kirsten D. Distance desert automata and the star height problem. Informatique Theorique et Applications. 2005, vol. 39, no. 3. pp. 455-509.

Bojanczyk M. Star height via games. ACM/IEEE Symposium on Logic in Computer Science (LICS). 2015, pp. 214-219.

Pin J.-E., Straubing H., Therien D. Some results on the generalized star-height problem. Information and Computation. 1992, vol. 101, no. 2, pp. 219-250.

Melnikov B. and Melnikova A. Pseudo-automata for generalized regular expressions. International Journal of Open Information Technologies. 2018, vol. 6, no. 1. pp. 1-8.

Salomaa A. Jewels of Formal Language Theory. Rockville (Maryland): Computer Science Press, Inc. 1981, 144 p.

Melnikov B. The complete finite automaton. International Journal of Open Information Technologies. 2017, vol. 5, no. 10. pp. 9-17.

Melnikov B. and Sayfullina M. O nekotoryh algoritmah ekvivalentnogo preobrazovaniya nedeterminirovannyh konechnyh avtomatov [On some algorithms for the equivalent transformation of nondeterministic finite automata]. Izvestiya of Higher Educational Institutions. Mathematics. 2009, no. 4, pp. 67-72. (in Russian)

Melnikov B. Extended nondeterministic finite automata. Fundamenta Informaticae. 2010, vol. 104, no. 3. pp. 255-265.

Dolgov V. and Melnikov B. Postroenie universal'nogo konechnogo avtomata ... [The construction of a universal finite automaton. Part I: From theory to practical algorithms]. Vestnik of Voronezh State University. 2013, no. 2, pp. 173-181. (in Russian)

Dolgov V., Melnikov B. and Melnikova A. Cikly grafa perehodov bazisnogo ... [Cycles of the transition graph of a basic automaton and related questions]. Vestnik of Voronezh State University. 2016, no. 4, pp. 95-111. (in Russian)


  • There are currently no refbacks.

Abava   FRUCT 2019

ISSN: 2307-8162