Reguläre Sprache Schließung
Kapitoly: Schließung von regulären Sprachen, Vereinheitlichung, Zugang zu, Der Unterschied, Ergänzung, Verkettung, Schlussfolgerung
Wir haben eine reguläre Sprache L. Wir beweisen, dass der Abschluss von L wiederum eine reguläre Sprache ist.
Was ist eine Sprachklausel?
Wir bezeichnen die Schließung der Sprache L als $L^\ast$. Die Schließung enthält alle Wörter, die durch Verkettung einer endlichen Anzahl von Wörtern der Sprache L zusammengesetzt werden können. Wir können eine Schließung definieren als:
$$ L^\ast = \left\{a_1\circ a_2 \circ \dots \circ a_n ,|, a_i \in L, n \in \mathbb{N}_0 \right\}, $$
wobei $\circ$ die Verkettungsoperation bezeichnet. Ein Abschluss enthält auch ein leeres Wort, d.h. ε.
Formales Verfahren
Wir werden ganz ähnlich vorgehen wie bei der Sprachverkettung. Nur verknüpfen wir nicht zwei verschiedene Automaten, sondern einen Automaten - und führen so Epsilon-Übergänge von den Endzuständen des Automaten zum Anfangszustand des Automaten. Allerdings muss die Schließung auch ein leeres Wort enthalten. Wie kann man das anordnen? Wir können den Anfangszustand zum Endzustand machen. Dann würde ein solcher Automat das leere Wort akzeptieren, aber er könnte auch ein anderes Wort akzeptieren. Deshalb erzeugen wir stattdessen einen neuen Anfangszustand und führen von diesem neuen Anfangszustand den Epsilon-Übergang zum ursprünglichen Anfangszustand.
Wir haben eine reguläre Sprache L1 und einen Automaten, der diese Sprache annimmt:
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \end{eqnarray}
Wir konstruieren einen nichtdeterministischen Automaten $A=\left<Q, \Sigma, \delta, q_s, F\right>$, für den Folgendes gilt:
- Q = Q1 ∪ {qs}
- $\Sigma = \Sigma_1$
- F = F1 ∪ {qs}
Wir definieren die Übergangsfunktion δ wie folgt:
$$ \delta(q, a) = \begin{cases} \delta_1(q, a)&\mbox{ Wenn }&q\in Q_1 \wedge q\notin F_1\\ \delta_1(q, a)&\mbox{ Wenn }&q\in F_1 \wedge a\ne \epsilon\\ \delta_1(q, a)\cup\left\{q_0\right\}&\mbox{ Wenn }&q\in F_1 \wedge a= \epsilon\\ \left\{q_0\right\}&\mbox{ Wenn }&q=q_s \wedge a= \epsilon\\ \emptyset&\mbox{ Wenn }&q=q_s \wedge a\ne \epsilon\\ \end{cases} $$
Beispiel
Betrachten wir diesen Automaten A1, der die Wörter 00 oder 11 akzeptiert:
Der Abschluss der Sprache L(A1) ist also die Sprache aller Wörter, die aus den Paaren 00 und 11 bestehen, z.B. 0000, 110011, 11110000, usw. Wir würden einen Automaten konstruieren, der diese Schließung akzeptiert, indem wir einen neuen Anfangszustand qs mit einem Epsilon-Übergang zum früheren Anfangszustand q0 erzeugen und Epsilon-Übergänge von den Zuständen q3 und q4 zum Zustand q0 hinzufügen:
Wir können überprüfen, dass dieser Automat tatsächlich die Wörter 0000, 110011, 11110000 akzeptiert, nicht aber beispielsweise 1010.