# Sternhöhe (computer science)

The star height is a term from theoretical computer science . It specifies the maximum of all nested applications of the Kleene star operator for a regular expression .

## definition

The star height sh (r) of a regular expression  r over a finite alphabet  A is recursively defined as

${\ displaystyle sh (\ emptyset) = 0}$ ${\ displaystyle sh (\ varepsilon) = 0}$ ${\ displaystyle sh (x) = 0 \ quad \ forall x \ in A}$ ${\ displaystyle sh (v \ cdot w) = max (sh (v), sh (w))}$ for all regular expressions ${\ displaystyle v, w}$ ${\ displaystyle sh (v | w) = max (sh (v), sh (w))}$ for all regular expressions ${\ displaystyle v, w}$ ${\ displaystyle sh (v ^ {\ star}) = sh (v) +1}$ for all regular expressions ${\ displaystyle v}$ Building on the astrolabe is a regular language defined as the minimum of all star levels , for a regular expression to exist. ${\ displaystyle sh (L)}$ ${\ displaystyle L}$ ${\ displaystyle n}$ ${\ displaystyle r \ in L}$ ${\ displaystyle sh (r) = n}$ ## Star altitude problem

The star height problem deals with the question of whether there is a maximum star height, i.e. whether there is one with for all regular languages over a fixed alphabet . If one does not exist, can the star height of a regular language be determined algorithmically ? ${\ displaystyle n}$ ${\ displaystyle sh (L) \ leq n}$ ${\ displaystyle L}$ ${\ displaystyle A}$ ${\ displaystyle n}$ Both questions have now been answered. In 1963 was LC Eggan show that such does not exist, by asking for each language with constructed. In 1988 Kosaburo Hashiguchi presented an algorithm with which the star height can be determined for a given regular language . ${\ displaystyle n}$ ${\ displaystyle n \ geq 0}$ ${\ displaystyle L_ {n}}$ ${\ displaystyle sh (L) = n}$ ${\ displaystyle L}$ ${\ displaystyle sh (L)}$ ## Generalized star height

The generalized (or generalized) star height is defined in the same way as the star height, but not via regular expressions, but via generalized regular expressions which, in addition to the normal operators, directly allow complementation ( ). The following applies: ${\ displaystyle gsh (r)}$ ${\ displaystyle \ neg}$ ${\ displaystyle gsh (\ emptyset) = 0}$ ${\ displaystyle gsh (\ varepsilon) = 0}$ ${\ displaystyle gsh (x) = 0 \ quad \ forall x \ in A}$ ${\ displaystyle gsh (\ lnot v) = gsh (v)}$ for all generalized regular expressions ${\ displaystyle v}$ ${\ displaystyle gsh (v \ cdot w) = max (gsh (v), gsh (w))}$ for all generalized regular expressions ${\ displaystyle v, w}$ ${\ displaystyle gsh (v | w) = max (gsh (v), gsh (w))}$ for all generalized regular expressions ${\ displaystyle v, w}$ ${\ displaystyle gsh (v \ cap w) = max (gsh (v), gsh (w))}$ for all generalized regular expressions ${\ displaystyle v, w}$ ${\ displaystyle gsh (v ^ {\ star}) = gsh (v) +1}$ for all generalized regular expressions ${\ displaystyle v}$ The generalized star height of a regular language is defined analogously . For example, the language has a star height of 1 while the same language has a generalized star height of 0 because of this. ${\ displaystyle gsh (L)}$ ${\ displaystyle L}$ ${\ displaystyle L (\ Sigma ^ {*})}$ ${\ displaystyle L (\ Sigma ^ {*}) = L (\ neg \ emptyset)}$ ## Generalized star height problem

The generalized star height problem is defined analogously to the star height problem, but in contrast to it, it is still unanswered. While there are regular languages with - for example, the language - open but is still the question of whether a regular language with existed. ${\ displaystyle L}$ ${\ displaystyle gsh (L) = 1}$ ${\ displaystyle {\ mathcal {L}} ((aa) ^ {*})}$ ${\ displaystyle L}$ ${\ displaystyle gsh (L) \ geq 2}$ ## literature

• Lawrence C. Eggan: Transition graphs and the star-height of regular events . In: Michigan Mathematical Journal 10, 1963, 4, , pp. 385-397, online (PDF; 1.2 MB), acc. August 8, 2010 .
• Kosaburo Hashiguchi: Algorithms for Determining Relative Star Height and Star Height . In: Information and computation 78, 1988, 2, , pp. 124-169.
• Jean-Eric Pin, Howard Straubing, Denis Thérien: Some results on the generalized star-height problem . In: Information and Computation 101, 1992, 2, , pp. 219-250, liafa.jussieu.fr