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   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

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

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

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
  • 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