Star height

The astrolabe is a term used in theoretical computer science. She admits a regular expression to the maximum of all nested applications of the Kleene star operator.

Definition

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

Based on the star height of a regular language is defined as the minimum of all star heights for which a regular expression exist.

Star height problem

The star height problem deals with the question of whether there is a maximum star level, so if one exists with for all regular languages ​​over a fixed alphabet. If such does not exist, the star height of a regular language can then be algorithmically determined?

Both questions are now answered. In 1963, LC Eggan was able to show that such does not exist, by constructing for each language with. Kosaburo Hashiguchi 1988 presented an algorithm with which the star height can be to a given regular language determine.

Generalized astrolabe

The generalized (or generalized ) star height is defined analogously to the star level, but not on regular expressions, but on generalized regular expressions, which allow addition to the normal operators directly complementation (). Thus:

The generalized star height of a regular language is defined analogously. For example, the language has the star height 1, while the same language because of the generalized star height 0.

Generalized star height problem

The generalized star height problem is defined analogously to the star height problem, but unlike the latter still unanswered. While there are regular languages ​​- for example the language - but is still open to question whether a regular language exists with.