Kleene-Stern einer regulären Sprache

Sei L eine reguläre Sprache. Wir beweisen, dass der Kleene-Stern der Sprache L wieder eine reguläre Sprache ist.

Was ist der Kleene-Stern einer Sprache

Den Kleene-Stern der Sprache L bezeichnen wir mit L^∗. Er enthält alle Wörter, die sich durch Verkettung endlich vieler Wörter aus der Sprache L zusammensetzen lassen. Den Kleene-Stern können wir so definieren:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in {\mathbb{N}}_0\},$$

wobei ∘ die Operation der Konkatenation bezeichnet. Der Kleene-Stern enthält auch das leere Wort, also ϵ.

Formales Vorgehen

Wir gehen sehr ähnlich vor wie bei der Konkatenation von Sprachen. Nur verbinden wir nicht zwei verschiedene Automaten, sondern einen einzigen Automaten – von den Endzuständen des Automaten führen wir ε-Übergänge in seinen Startzustand. Der Kleene-Stern muss aber auch das leere Wort enthalten. Wie lässt sich das erreichen? Wir könnten aus dem Startzustand einen Endzustand machen. Dann würde der Automat das leere Wort akzeptieren, aber möglicherweise auch weitere Wörter. Deshalb erzeugen wir stattdessen einen neuen Startzustand und führen von diesem neuen Startzustand einen ε-Übergang in den ursprünglichen Startzustand.

Wir haben eine reguläre Sprache L₁ und einen Automaten, der diese Sprache akzeptiert:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

Wir konstruieren einen nichtdeterministischen Automaten A = ⟨Q, Σ, δ, q_s, F⟩, für den gilt:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

Die Übergangsfunktion δ definieren wir so:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{falls}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{falls}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{falls}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{falls}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{falls}& q=q_s\wedge a\ne ϵ\end{array}$$

Beispiel

Gegeben sei dieser Automat A₁, der die Wörter 00 oder 11 akzeptiert:

Der Kleene-Stern der Sprache L(A₁) ist also die Sprache aller Wörter, die sich aus den Paaren 00 und 11 zusammensetzen, zum Beispiel 0000, 110011, 11110000 usw. Den Automaten, der diesen Kleene-Stern akzeptiert, würden wir so konstruieren, dass wir einen neuen Startzustand q_s mit einem ε-Übergang in den ehemaligen Startzustand q₀ erzeugen und ε-Übergänge von den Zuständen q₃ und q₄ in den Zustand q₀ hinzufügen:

Wir können überprüfen, dass dieser Automat tatsächlich die Wörter 0000, 110011, 11110000 akzeptiert, aber zum Beispiel das Wort 1010 nicht.

Quellen

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools