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

$sh(\emptyset) = 0$

sh(ε) = 0

$sh(x) = 0 \quad \forall x \in A$

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

sh(v | w) = max(sh(v),sh(w)) für alle regulären Ausdrücke v,w

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

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

Sternhöhenproblem

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

Verallgemeinerte Sternhöhe

Die verallgemeinerte Sternhöhe gsh(r) ist analog zur Sternhöhe definiert, allerdings nicht über regulären Ausdrücken, sondern über verallgemeinerten regulären Ausdrücken. Es gilt also:

$sh(\emptyset) = 0$

sh(ε) = 0

$sh(x) = 0 \quad \forall x \in A$

$sh(\lnot v) = sh(v)$ für alle verallgemeinerten regulären Ausdrücke v

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

sh(v | w) = max(sh(v),sh(w)) für alle verallgemeinerten regulären Ausdrücke v,w

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

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

Analog ist die verallgemeinerte Sternhöhe gsh(L) einer regulären Sprache L definiert.

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 gsh(L) = 1 – zum Beispiel die Sprache $\mathcal{L}((aa)^*)$ –, offen ist aber noch die Frage, ob auch eine reguläre Sprache L mit $gsh(L)\geq 2$ existiert.

Literatur

• Lawrence C. Eggan: Transition graphs and the star-height of regular events. In: Michigan Mathematical Journal 10, 1963, 4, ISSN 0026-2285, 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, ISSN 0890-5401, 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, ISSN 0890-5401, S. 219–250, liafa.jussieu.fr