Wikipedia · einfach zusammengefasst · Stand
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 …
Inhalt4 Abschnitte
Grundidee und Definition
Die Sternhöhe ist ein Begriff der theoretischen Informatik. Sie misst bei einem regulären Ausdruck die größte Zahl verschachtelter Anwendungen des Kleene-Stern-Operators. Der Kleene-Stern v* steht dabei für beliebig viele Wiederholungen des Ausdrucks v.
Für einen regulären Ausdruck r über einem endlichen Alphabet A wird die Sternhöhe sh(r) rekursiv festgelegt: sh(∅)=0, sh(ε)=0 und sh(x)=0 für alle x∈A. Die Grundbausteine leerer Ausdruck, leeres Wort ε und einzelne Zeichen haben also keine Sternverschachtelung.
Bei Verknüpfungen wird der größere der beiden Werte übernommen: sh(v·w)=max(sh(v), sh(w)) für Konkatenation und sh(v|w)=max(sh(v), sh(w)) für Alternative. Dagegen erhöht ein Stern die Höhe um eins: sh(v*)=sh(v)+1. Entscheidend ist somit nicht die Anzahl aller Sterne, sondern ihre tiefste Verschachtelung.
Sternhöhe einer Sprache und das Sternhöhenproblem
Die Sternhöhe einer regulären Sprache L, sh(L), ist das Minimum aller Sternhöhen n, für die ein regulärer Ausdruck r mit sh(r)=n existiert, der die Sprache beschreibt. Gesucht wird also stets eine möglichst wenig verschachtelte Darstellung der Sprache.
Das Sternhöhenproblem fragte zunächst, ob es für alle regulären Sprachen über einem festen Alphabet A eine gemeinsame obere Schranke n gibt, also ob stets sh(L)≤n gilt. Falls es keine solche Schranke gibt, lautete die zweite Frage, ob sich die Sternhöhe einer regulären Sprache trotzdem algorithmisch bestimmen lässt.
Beide Fragen sind beantwortet: L. C. Eggan zeigte 1963, dass keine maximale Sternhöhe existiert. Er konstruierte für jedes n≥0 eine Sprache Lₙ mit Sternhöhe n. Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor, mit dem sich für eine gegebene reguläre Sprache L die Sternhöhe sh(L) bestimmen lässt.
Verallgemeinerte Sternhöhe
Die verallgemeinerte oder generalisierte Sternhöhe gsh(r) wird für verallgemeinerte reguläre Ausdrücke definiert. Diese erlauben zusätzlich zu den üblichen Operatoren direkt die Komplementierung ¬. Das Komplement eines Ausdrucks umfasst die Wörter über dem betrachteten Alphabet, die nicht zu seiner Sprache gehören.
Auch hier gilt gsh(∅)=0, gsh(ε)=0 und gsh(x)=0 für alle x∈A. Die Komplementierung verändert die Höhe nicht: gsh(¬v)=gsh(v). Für Konkatenation, Alternative und Schnitt gilt jeweils der Maximalwert der Teilausdrücke: gsh(v·w)=max(gsh(v),gsh(w)), gsh(v|w)=max(gsh(v),gsh(w)) und gsh(v∩w)=max(gsh(v),gsh(w)). Ein Kleene-Stern erhöht die Höhe wieder um eins: gsh(v*)=gsh(v)+1.
Die verallgemeinerte Sternhöhe gsh(L) einer regulären Sprache L wird analog als kleinste erreichbare Höhe definiert. Die Sprache L(Σ*) hat Sternhöhe 1. Weil jedoch L(Σ*)=L(¬∅) gilt, besitzt dieselbe Sprache die verallgemeinerte Sternhöhe 0: Die direkte Komplementierung kann also eine Sternanwendung überflüssig machen.
Offene Frage zur verallgemeinerten Sternhöhe
Das verallgemeinerte Sternhöhenproblem entspricht dem Sternhöhenproblem, ist jedoch noch nicht vollständig gelöst. Bekannt ist, dass es reguläre Sprachen L mit gsh(L)=1 gibt. Ein Beispiel ist die Sprache ℒ((aa)*).
Offen bleibt, ob es überhaupt eine reguläre Sprache L mit gsh(L)≥2 gibt. Damit ist insbesondere ungeklärt, ob bei verallgemeinerten regulären Ausdrücken eine Sternverschachtelung von mindestens zwei unvermeidbar sein kann.