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 | Quelltext bearbeiten]

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

für alle regulären Ausdrücke
für alle regulären Ausdrücke
für alle regulären Ausdrücke

Darauf aufbauend ist die Sternhöhe einer regulären Sprache definiert als das Minimum aller Sternhöhen , für das ein regulärer Ausdruck mit existiert.

Sternhöhenproblem[Bearbeiten | Quelltext bearbeiten]

Das Sternhöhenproblem behandelt die Frage, ob es eine maximale Sternhöhe gibt, also ob ein mit für alle regulären Sprachen über einem festen Alphabet existiert. Falls ein solches 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 nicht existiert, indem er für jedes eine Sprache mit konstruierte. Kosaburo Hashiguchi stellte 1988 einen Algorithmus vor, mit dem sich zu einer gegebenen regulären Sprache die Sternhöhe bestimmen lässt.

Verallgemeinerte Sternhöhe[Bearbeiten | Quelltext bearbeiten]

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

für alle verallgemeinerten regulären Ausdrücke
für alle verallgemeinerten regulären Ausdrücke
für alle verallgemeinerten regulären Ausdrücke
für alle verallgemeinerten regulären Ausdrücke
für alle verallgemeinerten regulären Ausdrücke

Analog ist die verallgemeinerte Sternhöhe einer regulären Sprache definiert. Beispielsweise hat die Sprache die Sternhöhe 1, während dieselbe Sprache wegen die verallgemeinerte Sternhöhe 0 hat.

Verallgemeinertes Sternhöhenproblem[Bearbeiten | Quelltext bearbeiten]

Das verallgemeinerte Sternhöhenproblem ist analog zum Sternhöhenproblem definiert, aber im Gegensatz zu diesem noch unbeantwortet. Zwar gibt es reguläre Sprachen mit – zum Beispiel die Sprache –, offen ist aber noch die Frage, ob auch eine reguläre Sprache mit existiert.

Literatur[Bearbeiten | Quelltext 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