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