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 $\mathrm{sh}(r)$ eines regulären Ausdrucks r über einem endlichen Alphabet A ist rekursiv definiert als

$\mathrm{sh}(\mathrm{\varnothing })=0$

$\mathrm{sh}(\epsilon )=0$

$\mathrm{sh}(x)=0\mathrm{\forall }x\in A$

$\mathrm{sh}(v\cdot w)=\max (\mathrm{sh}(v),\mathrm{sh}(w))$ für alle regulären Ausdrücke $v,w$

$\mathrm{sh}(v|w)=\max (\mathrm{sh}(v),\mathrm{sh}(w))$ für alle regulären Ausdrücke $v,w$

$\mathrm{sh}(v^{\star })=\mathrm{sh}(v)+1$ für alle regulären Ausdrücke $v$

Darauf aufbauend ist die Sternhöhe $\mathrm{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 $\mathrm{sh}(r)=n$ existiert.

Sternhöhenproblem

Das Sternhöhenproblem behandelt die Frage, ob es eine maximale Sternhöhe gibt, also ob ein $n$ mit $\mathrm{sh}(L)\le 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\ge 0$ eine Sprache $L_n$ mit $\mathrm{sh}(L)=n$ konstruierte. Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor, mit dem sich zu einer gegebenen regulären Sprache $L$ die Sternhöhe $\mathrm{sh}(L)$ bestimmen lässt.

Verallgemeinerte Sternhöhe

Die verallgemeinerte (oder auch generalisierte) Sternhöhe $\mathrm{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 ($\mathrm{\neg }$) erlauben. Es gilt also:

$\mathrm{gsh}(\mathrm{\varnothing })=0$

$\mathrm{gsh}(\epsilon )=0$

$\mathrm{gsh}(x)=0\mathrm{\forall }x\in A$

$\mathrm{gsh}(\mathrm{\neg }v)=\mathrm{gsh}(v)$ für alle verallgemeinerten regulären Ausdrücke $v$

$\mathrm{gsh}(v\cdot w)=\max (\mathrm{gsh}(v),\mathrm{gsh}(w))$ für alle verallgemeinerten regulären Ausdrücke $v,w$

$\mathrm{gsh}(v|w)=\max (\mathrm{gsh}(v),\mathrm{gsh}(w))$ für alle verallgemeinerten regulären Ausdrücke $v,w$

$\mathrm{gsh}(v\cap w)=\max (\mathrm{gsh}(v),\mathrm{gsh}(w))$ für alle verallgemeinerten regulären Ausdrücke $v,w$

$\mathrm{gsh}(v^{\star })=\mathrm{gsh}(v)+1$ für alle verallgemeinerten regulären Ausdrücke $v$

Analog ist die verallgemeinerte Sternhöhe $\mathrm{gsh}(L)$ einer regulären Sprache $L$ definiert. Beispielsweise hat die Sprache $L({\mathrm{\Sigma }}^{*})$ die Sternhöhe 1, während dieselbe Sprache wegen $L({\mathrm{\Sigma }}^{*})=L(\mathrm{\neg }\mathrm{\varnothing })$ 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 $\mathrm{gsh}(L)=1$, zum Beispiel die Sprache $ℒ((aa{)}^{*})$. Offen ist aber noch die Frage, ob auch eine reguläre Sprache $L$ mit $\mathrm{gsh}(L)\ge 2$ existiert.

Literatur

• Lawrence C. Eggan: Transition graphs and the star-height of regular events. In: Michigan Mathematical Journal 10, 1963, 4, Vorlage:ISSN, S. 385–397, online (PDF; 1,2 MB), acc. 8. August 2010.
• Kosaburo Hashiguchi: Algorithms for Determining Relative Star Height and Star Height. In: Information and computation 78, 1988, 2, Vorlage:ISSN, S. 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, Vorlage:ISSN, S. 219–250, liafa.jussieu.fr