Sternhöhe (Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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

sh(\emptyset) = 0
sh(\varepsilon) = 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[Bearbeiten]

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[Bearbeiten]

Die verallgemeinerte (oder auch generalisierte) Sternhöhe 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:

gsh(\emptyset) = 0
gsh(\varepsilon) = 0
gsh(x) = 0 \quad \forall x \in A
gsh(\lnot v) = gsh(v) für alle verallgemeinerten regulären Ausdrücke v
gsh(v\cdot w) = max(gsh(v),gsh(w)) für alle verallgemeinerten regulären Ausdrücke v, w
gsh(v | w) = max(gsh(v),gsh(w)) für alle verallgemeinerten regulären Ausdrücke v, w
gsh(v\cap w) = max(gsh(v),gsh(w)) für alle verallgemeinerten regulären Ausdrücke v, w
gsh(v^\star) = gsh(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. 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[Bearbeiten]

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[Bearbeiten]

  • 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