Regular languages of star height one. (English) Zbl 0547.68072

Hashiguchi, K.

Inf. Control 53, 199-210 (1982).

The paper studies the old and so far open problem of determining the star height of a given regular language. The author shows that for any regular language R, there exists a regular expression E in string form such that (1) E denotes R, (2) the star height of E is equal to that of R, and (3) for any word w which appears in E, \(l(w)\leq 16m(m+2)(h(R)m(m+2)+1),\) where l(w) is the length of w, h(R) is the star height of R, and m is the number of elements of the syntactic semigroup of R. This result together with a theorem in the paper ”Representation theorems on regular languages” by K. Hashiguchi [J. Comput. Syst. Sci. 27, 101-115 (1983; Zbl 0516.68063)] provides an algorithm for deciding whether a given regular language is of star height one.

Reviewer: M.Linna

MSC:

68Q45

Formal languages and automata

Keywords:

star height; regular language

Citations:

Zbl 0516.68063