Das Sternhöhe-Problem in der formellen Sprachtheorie ist die Frage, ob alle regelmäßigen Sprachen mit regelmäßigen Ausdrücken der beschränkten Sternhöhe, d. h. mit einer beschränkten nistenden Tiefe von Sternen von Kleene ausgedrückt werden können. Spezifisch, ist eine nistende Tiefe ein immer genügend? Wenn nicht, gibt es ein Algorithmus, um zu bestimmen, wie viele sind erforderlich? Das Problem wurde dadurch erhoben.

Familien von regelmäßigen Sprachen mit der unbegrenzten Sternhöhe

Die erste Frage wurde verneint, als 1963 Eggan Beispiele von regelmäßigen Sprachen der Sternhöhe n für jeden n angeführt hat. Hier wird die Sternhöhe h (L) einer regelmäßigen Sprache L als die minimale Sternhöhe unter allen regelmäßigen Ausdrücken definiert, die L vertreten. Die ersten paar Sprachen, die dadurch gefunden sind, werden im folgenden, mittels des Gebens eines regelmäßigen Ausdrucks für jede Sprache beschrieben:

:

e_1 &= a_1^* \\

e_2 &= \left (a_1^*a_2^*a_3\right) ^* \\

e_3 &= \left (\left (a_1^*a_2^*a_3\right) ^*\left (a_4^*a_5^*a_6\right) ^*a_7\right) ^* \\

e_4 &= \left (

\left (\left (a_1^*a_2^*a_3\right) ^*\left (a_4^*a_5^*a_6\right) ^*a_7\right) ^ *

\left (\left (a_8^*a_9^*a_ {10 }\\Recht) ^*\left (a_ {11} ^*a_ {12} ^*a_ {13 }\\Recht) ^*a_ {14 }\\Recht) ^ *

a_ {15 }\\Recht) ^ *

\end {alignat }\

</Mathematik>

Der Baugrundsatz für diese Ausdrücke ist, dass Ausdruck durch concatening zwei Kopien erhalten wird, passend die Briefe der zweiten Kopie mit frischen Alphabet-Symbolen umbenennend, das Ergebnis mit einem anderen frischen Alphabet-Symbol, und dann durch die Umgebung des resultierenden Ausdrucks mit einem Stern von Kleene verkettend. Der restliche, schwierigere Teil, soll beweisen, dass für es keinen gleichwertigen regelmäßigen Ausdruck der Sternhöhe weniger gibt als n; ein Beweis wird eingereicht.

Jedoch verwenden die Beispiele von Eggan ein großes Alphabet, der Größe 2-1 für die Sprache mit der Sternhöhe n. Er hat so gefragt, ob wir auch Beispiele über binäre Alphabete finden können. Wie man bewies, war das kurz später dadurch wahr.

Ihre Beispiele können von einer induktiv definierten Familie von regelmäßigen Ausdrücken über das binäre Alphabet wie folgt vgl beschrieben werden.:

:

e_1 & = (ab) ^* \\

e_2 & = \left (aa (ab) ^*bb (ab) ^*\right) ^* \\

e_3 & = \left (aaaa \left (aa (ab) ^*bb (ab) ^*\right) ^* bbbb \left (aa (ab) ^*bb (ab) ^*\right) ^*\right) ^* \\

\& \cdots \\

e_ {n+1} & = (\, \underbrace {a\cdots} _ {2^n }\\, \cdot \, e_n \, \cdot \, \underbrace {b\cdots b} _ {2^n }\\, \cdot \, e_n \,) ^ *

\end {alignat }\</Mathematik>

Wieder ist ein strenger Beweis für die Tatsache erforderlich, die keinen gleichwertigen regelmäßigen Ausdruck der niedrigeren Sternhöhe zulässt. Beweise werden nach und nach gegeben.

Die Computerwissenschaft der Sternhöhe von regelmäßigen Sprachen

Im Gegensatz hat sich die zweite Frage erwiesen, viel schwieriger zu sein, und die Frage ist ein berühmtes offenes Problem in der formellen Sprachtheorie seit mehr als zwei Jahrzehnten geworden. Seit Jahren gab es nur wenig Fortschritt. Die Sprachen der reinen Gruppe waren die erste interessante Familie von regelmäßigen Sprachen, für die, wie man bewies, das Sternhöhe-Problem entscheidbar war. Aber das allgemeine Problem ist offen seit mehr als 25 Jahren geblieben, bis es von Hashiguchi gesetzt wurde, der 1988 einen Algorithmus veröffentlicht hat, um die Sternhöhe jeder regelmäßigen Sprache zu bestimmen. Der Algorithmus war überhaupt nicht praktisch, von der nichtelementaren Kompliziertheit seiend. Um den riesigen Quellenverbrauch dieses Algorithmus zu illustrieren, geben die Lombardei und Sakarovitch (2002) einige wirkliche Zahlen:

Bemerken Sie, dass allein die Zahl 10 Milliarden Nullen, wenn niedergeschrieben, in der dezimalen Notation hat, und bereits bei weitem größer ist als die Zahl von Atomen im erkennbaren Weltall.

Ein viel effizienterer Algorithmus als das Verfahren von Hashiguchi wurde von Kirsten 2005 ausgedacht. Dieser Algorithmus Läufe, für einen gegebenen nichtdeterministischen begrenzten Automaten, wie eingegeben, innerhalb des Doppelt-Exponentialraums. Und doch überschreiten die Quellenvoraussetzungen dieses Algorithmus noch außerordentlich die Ränder dessen, was praktisch ausführbar betrachtet wird.

Siehe auch

• Verallgemeinertes Sternhöhe-Problem
• (technische Berichtsversion)