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
- for all regular expressions
- for all regular expressions
- for all regular expressions
Building on the astrolabe is a regular language defined as the minimum of all star levels , for a regular expression to exist.
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 ?
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 .
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:
- for all generalized regular expressions
- for all generalized regular expressions
- for all generalized regular expressions
- for all generalized regular expressions
- for all generalized regular expressions
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.
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.
literature
- Lawrence C. Eggan: Transition graphs and the star-height of regular events . In: Michigan Mathematical Journal 10, 1963, 4, ISSN 0026-2285 , 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, ISSN 0890-5401 , 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, ISSN 0890-5401 , pp. 219-250, liafa.jussieu.fr