Sternhöhe (Informatik)
# Sternhöhe (Informatik)

Die Sternhöhe ist ein Begriff aus der Theoretischen Informatik. Sie gibt zu einem regulären Ausdruck das Maximum aller verschachtelten Anwendungen des Kleene-Stern-Operators an.

## Definition

Die Sternhöhe $\operatorname {sh} (r)$ eines regulären Ausdrucks r über einem endlichen Alphabet A ist rekursiv definiert als

    $\operatorname {sh} (\emptyset )=0$
    $\operatorname {sh} (\varepsilon )=0$
    $\operatorname {sh} (x)=0\quad \forall x\in A$
    $\operatorname {sh} (v\cdot w)=\max(\operatorname {sh} (v),\operatorname {sh} (w))$ für alle regulären Ausdrücke $v,w$
    $\operatorname {sh} (v|w)=\max(\operatorname {sh} (v),\operatorname {sh} (w))$ für alle regulären Ausdrücke $v,w$
    $\operatorname {sh} (v^{\star })=\operatorname {sh} (v)+1$ für alle regulären Ausdrücke $v$

Darauf aufbauend ist die Sternhöhe $\operatorname {sh} (L)$ einer regulären Sprache $L$ definiert als das Minimum aller Sternhöhen $n$, für das ein regulärer Ausdruck $r\in L$ mit $\operatorname {sh} (r)=n$ existiert.

## Sternhöhenproblem

Das Sternhöhenproblem behandelt die Frage, ob es eine maximale Sternhöhe gibt, also ob ein $n$ mit $\operatorname {sh} (L)\leq n$ für alle regulären Sprachen $L$ über einem festen Alphabet $A$ existiert. Falls ein solches $n$ nicht existiert, lässt sich dann die Sternhöhe einer regulären Sprache algorithmisch bestimmen?

Beide Fragen sind mittlerweile beantwortet. Im Jahre 1963 konnte L. C. Eggan zeigen, dass ein solches $n$ nicht existiert, indem er für jedes $n\geq 0$ eine Sprache $L_{n}$ mit $\operatorname {sh} (L)=n$ konstruierte. Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor, mit dem sich zu einer gegebenen regulären Sprache $L$ die Sternhöhe $\operatorname {sh} (L)$ bestimmen lässt.

## Verallgemeinerte Sternhöhe

Die verallgemeinerte (oder auch generalisierte) Sternhöhe $\operatorname {gsh} (r)$ ist analog zur Sternhöhe definiert, allerdings nicht über regulären Ausdrücken, sondern über verallgemeinerten regulären Ausdrücken, welche zusätzlich zu den normalen Operatoren direkt die Komplementierung ($\neg$) erlauben. Es gilt also:

    $\operatorname {gsh} (\emptyset )=0$
    $\operatorname {gsh} (\varepsilon )=0$
    $\operatorname {gsh} (x)=0\quad \forall x\in A$
    $\operatorname {gsh} (\lnot v)=\operatorname {gsh} (v)$ für alle verallgemeinerten regulären Ausdrücke $v$
    $\operatorname {gsh} (v\cdot w)=\max(\operatorname {gsh} (v),\operatorname {gsh} (w))$ für alle verallgemeinerten regulären Ausdrücke $v,w$
    $\operatorname {gsh} (v|w)=\max(\operatorname {gsh} (v),\operatorname {gsh} (w))$ für alle verallgemeinerten regulären Ausdrücke $v,w$
    $\operatorname {gsh} (v\cap w)=\max(\operatorname {gsh} (v),\operatorname {gsh} (w))$ für alle verallgemeinerten regulären Ausdrücke $v,w$
    $\operatorname {gsh} (v^{\star })=\operatorname {gsh} (v)+1$ für alle verallgemeinerten regulären Ausdrücke $v$

Analog ist die verallgemeinerte Sternhöhe $\operatorname {gsh} (L)$ einer regulären Sprache $L$ definiert. Beispielsweise hat die Sprache $L(\Sigma ^{*})$ die Sternhöhe 1, während dieselbe Sprache wegen $L(\Sigma ^{*})=L(\neg \emptyset )$ die verallgemeinerte Sternhöhe 0 hat.

## Verallgemeinertes Sternhöhenproblem

Das verallgemeinerte Sternhöhenproblem ist analog zum Sternhöhenproblem definiert, aber im Gegensatz zu diesem noch unbeantwortet. Zwar gibt es reguläre Sprachen $L$ mit $\operatorname {gsh} (L)=1$, zum Beispiel die Sprache ${\mathcal {L}}((aa)^{*})$. Offen ist aber noch die Frage, ob auch eine reguläre Sprache $L$ mit $\operatorname {gsh} (L)\geq 2$ existiert.

