1. Welt
  2. Argumentationen
  3. #1452
Alexander Fufaev

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

aus dem Bereich: Argumentationen
Mehr dazu

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\).

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 7
Gäste online: 7
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.