Direkt zum Inhalt
  1. Startseite
  2. Argumentationen
  3. #333

Herleitung Abschlusseigenschaften (Schnitt, Vereinigung, ...) für reguläre Sprachen

Was du hier lernst...
  1. Abgeschlossenheit unter Komplement
  2. Abgeschlossenheit unter Vereinigung
  3. Abgeschlossenheit unter Schnitt

Beweis der Abgeschlossenheit der regulären Sprachen unter Komplement, Schnitt, Vereinigung etc. lässt sich über die regulären Grammatiken, reguläre Ausdrücke oder deterministische endliche Automaten (DEA) bewerkstelligen.

Abgeschlossenheit unter Komplement

Für alle regulären Sprachen \(L\) ist das Komplement \(\bar{L}\) auch regulär.

Beweis
Für jede reguläre Sprache \(L\) (Typ-3-Sprache) lässt sich ein deterministischer endlicher Automat (DEA) konstruieren.

Konstruiere also für die reguläre Sprache \(L\) einen deterministischen endlichen Automaten \(A\) mit \(L(A)\), der alle Wörter \(w\) aus \(L\) akzeptiert:1\[ A = (Z, \Sigma, \delta, z_0, E) \]

Konstuiere nun folgenden DEA:2\[ \bar{A} = (Z, \Sigma, \delta, z_0, \bar{E}) \]

Das heißt - die Menge der Endzustände \(\bar{E}\) des Automaten \(\bar{A}\) ist so gewählt, dass diese alle Zustände aus \(Z\) enthält, die nicht die Endzustände des Automaten \(A\) sind: \(\bar{E} = Z \backslash E \).

Der Automat \(\bar{A}\) akzeptiert also ein Wort \(w\) genau dann, wenn dieses nicht in der Sprache \(L\) ist: \(w \notin L \). Damit akzeptiert \(\bar{A}\) alle Wörter des Komplments von \(L\): \(w \in \bar{L}\).

Da es möglich war, ein DEA \(\bar{A}\) für die Komplementsprache \(\bar{L}\) anzugeben, muss \(\bar{L}\) regulär sein.

Abgeschlossenheit unter Vereinigung

Für zwei reguläre Sprachen \(L_1\) und \(L_2\) ist deren Vereinigung \(L_1 \cup L_2\) auch regulär.

Beweis
Die Definition einer regulären Sprache ist: Eine Sprache heißt regulär genau dann, wenn es eine reguläre Grammatik \(G\) gibt, mit \(L = L(G)\). (Das heißt: \(G\) erzeugt \(L\)).

Da \(L_1\) und \(L_2\) reguläre Sprache sind, existieren die Grammatiken \(G_1 = (V_1, \Sigma, P_1, S_1)\) und \(G_2 = (V_2, \Sigma, P_2, S_2)\), die jeweils \(L_1\) und \(L_2\) erzeugen: \(L_1 = L_1(G_1)\) und \(L_2 = L_2(G_2)\).

Das Ziel ist es eine reguläre Grammatik \(G\) für die Sprche \(L_1 \cup L_2\) zu konstuieren. Da es um die Vereinigung beider Sprachen geht, wird die Vereinigung ihrer Produktionsmengen \(P_1\) und \(P_2\) gebildet. Außerdem wird noch die einelementige Menge \(\{S \rightarrow S_1 | S_2\}\) dazu genommen, um eine neue Starvariable \(S\) einzuführen. Diese wird auf \(S_1\) oder \(S_2\) abgebildet, die keine Starvariablen von \(G\) sind. Die Produktionsmenge von \(G\) ist also:3\[ P_1 \cup P_2 \cup \{S \rightarrow S_1 | S_2\} \]

Die Menge der Variablen von \(G\) ist dann:4\[ V_1 \cup V_2 \cup \{S\} \]

Mit dieser Konstuktion der Produktionsmenge 3 und der Variablenmenge 4, lässt sich eine reguläre Grammatik \(G\) angeben, die die Sprache \(L_1 \cup L_2\) erzeugt:5\[ G = (V_1 \cup V_2 \cup \{S\},~ \Sigma,~ P_1 \cup P_2 \cup \{S \rightarrow S_1 | S_2\},~ S) \]

Damit ist \(L_1 \cup L_2\) regulär.

Abgeschlossenheit unter Schnitt

Für zwei reguläre Sprachen \(L_1\) und \(L_2\) ist deren Schnitt \(L_1 \cap L_2\) auch regulär.

Beweis
Der Schnitt lässt sich nun leicht mit den bewiesenen Abschlusseigenschaften für Komplement und Vereinigung sowie dem folgenden Zusammenhang zeigen:6\[ L_1 \cap L_2 = \overline{\bar{L}_1 \cup \bar{L}_2} \](6 ist einfach mit einem Mengendiagramm nachvollziehbar).

Da \(L_1\) und \(L_2\) regulär sind, sind deren Komplemente \( \bar{L}_1 \) und \( \bar{L}_2 \) auch regulär. Die Vereinigung \(\bar{L}_1 \cup \bar{L}_2\) zweier regulärer Sprachen ist auch regulär. Das Komplement \(\overline{\bar{L}_1 \cup \bar{L}_2}\) einer regulären Mengen \(\bar{L}_1 \cup \bar{L}_2\) ist regulär. Die rechte Seite von 6 ist damit regulär und folglich auch der Schnitt \(L_1 \cap L_2\).

Details zum Inhalt
  • Copyright: ©2020
  • Lizenz: CC BY 4.0Dieser Inhalt darf mit der Angabe des Copyrights weiterverwendet werden!
  • Dieser Inhalt wurde hinzugefügt von FufaeV am .
  • Dieser Inhalt wurde aktualisiert von FufaeV am .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?