Vereinigung regulärer Sprachen

Gegeben seien zwei reguläre Sprachen L₁, L₂. Wir beweisen, dass ihre Vereinigung L = L₁ ∪ L₂ ebenfalls eine reguläre Sprache ist.

Vorgehen mit einem deterministischen Automaten

Idee des Vorgehens

Wir haben zwei reguläre Sprachen L₁ und L₂ und wollen beweisen, dass ihre Vereinigung L₁ ∪ L₂ wieder eine reguläre Sprache ist. Da L₁ und L₂ reguläre Sprachen sind, gibt es endliche Automaten A₁ und A₂, die die Sprachen L₁ und L₂ akzeptieren, es gilt also L(A₁) = L₁ und L(A₂) = L₂. Wir konstruieren nun einen endlichen Automaten A, der die Sprache L₁ ∪ L₂ akzeptiert, und beweisen damit, dass die Sprache L₁ ∪ L₂ regulär ist.

Wie gehen wir vor? Wir haben die endlichen Automaten A₁ und A₂, die die einzelnen Sprachen akzeptieren. Wir können sagen, dass ein Wort w genau dann zur Sprache L₁ ∪ L₂ gehört, wenn es mindestens einer der Automaten A₁ oder A₂ akzeptiert.

Der Automat A könnte so funktionieren, dass er für die Eingabe w die Berechnung des Automaten A₁ für die Eingabe w simuliert. Akzeptiert A₁ das Wort w, dann akzeptiert auch A das Wort w. Lehnt A₁ das Wort w ab, dann versucht A noch, die Berechnung von A₂ für die Eingabe w zu simulieren. Akzeptiert A₂ das Wort w, dann akzeptiert auch A das Wort w. Andernfalls lehnt er ab.

Es bleibt noch zu formalisieren, was es bedeutet, dass der Automat A die Berechnung eines anderen Automaten „simuliert“.

Formalisierung

Wir haben zwei reguläre Sprachen L₁ und L₂, die von den folgenden endlichen Automaten akzeptiert werden:

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Wir konstruieren den endlichen Automaten A = ⟨Q, Σ, δ, q, F⟩, der die Sprache L = L₁ ∪ L₂ akzeptiert. Wir nutzen die Idee, zwei Automaten A₁, A₂ zu simulieren. Stellen wir uns also vor, dass wir das Wort w = w₁w₂… w_n als Eingabe haben und nun gleichzeitig den Ablauf der Automaten A₁ und A₂ für das Wort w simulieren. Die Anfangskonfiguration des Automaten A₁ ist ⟨q₁, w₁w₂… w_n⟩, die Anfangskonfiguration von A₂ ist ⟨q₂, w₁w₂… w_n⟩. In jedem Automaten führen wir nun einen Rechenschritt aus und gelangen so in die Konfigurationen ⟨δ₁(q₁, w₁), w₂… w_n⟩ und ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Wir sehen, dass sich diese Konfigurationen nur in der ersten Komponente unterscheiden, die zweite – der ungelesene Teil des Wortes – ist bei beiden immer gleich. Während der Simulation müssen wir also nicht zwei Konfigurationen zweier Automaten mitführen, sondern es genügt uns eine Konfiguration der Form ⟨⟨q_i, q_j⟩, w_l… w_n⟩, wobei q_i ∈ Q₁ und q_j ∈ Q₂. Mit anderen Worten: Unser konstruierter Automat A hat die Anfangskonfiguration ⟨⟨q₁, q₂⟩, w⟩. Der erste Teil des Paares ⟨q₁, q₂⟩ stellt den Zustand dar, in dem sich der Automat A₁ gerade befindet, und die zweite Komponente den aktuellen Zustand des Automaten A₂.

Wir können also schreiben, dass der konstruierte Automat A die Zustandsmenge Q = Q₁ × Q₂ hat. Das ist das kartesische Produkt der Zustände der beiden vorherigen Automaten. Die folgende Idee ist: Der Automat A hat den Startzustand ⟨q₁, q₂⟩, und wenn der Automat A₁ für das Symbol w₁ in den Zustand q_i übergeht und der Automat A₂ für das Symbol w₁ in den Zustand q_j übergeht, dann geht der Automat A für das Symbol w₁ in den Zustand ⟨q_i, q_j⟩ über.

Die Übergangsfunktion δ schreiben wir so (hier setzen wir schon voraus, dass wir uns gerade in den Zuständen q_i und q_j befinden):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Es bleiben nur noch Kleinigkeiten. Für das Alphabet gilt Σ= Σ₁ ∪ Σ₂. Der Startzustand ist q = ⟨q₁, q₂⟩. Und die Endzustände sind alle Paare ⟨q_i, q_j⟩, für die q_i ∈ F₁ oder q_j ∈ F₂ gilt.

Veranschaulichung des Vorgehens

Gegeben seien zwei Automaten. Der erste ist der Automat A₁, der alle Wörter akzeptiert (einschließlich des leeren Wortes), in denen sich Nullen und Einsen abwechseln, d. h. Wörter der Form 01, 0101, 010101, …

Der andere Automat A₂ akzeptiert Wörter, die mindestens eine Null enthalten:

Die Vereinigung dieser Sprachen besteht aus den Wörtern, die entweder eine Null enthalten oder die Form 01, 0101, … haben. Nun konstruieren wir den endlichen Automaten A = ⟨Q, Σ, δ, q, F⟩, der genau diese vereinigte Sprache akzeptiert. Zuerst zeigen wir, wie die Zustände dieses neuen Automaten A aussehen. Es ist das kartesische Produkt der Zustände des ersten und des zweiten Automaten:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

So sehen die sechs Zustände des Automaten A aus, der die vereinigte Sprache L(A₁) ∪ L(A₂) akzeptiert. Im Diagramm sähen sie so aus:

Lass dich nicht davon verwirren, dass wir Zustände haben, die aus Paaren von Zuständen bestehen – das dient nur der besseren Übersicht darüber, was im Automaten eigentlich passiert. Die Zustände könnten ruhig ganz klassisch q₀, …, q₅ heißen. Endzustände sind die Zustände, die entweder den Zustand q₀ oder p₁ enthalten, also die Endzustände der ursprünglichen Automaten. Der Startzustand ist ⟨q₀, p₀⟩.

Nun müssen wir alle Übergänge finden. Wir schreiben uns eine solche Tabelle auf:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Und füllen die Tabelle nach und nach aus. Zuerst stellen wir fest, wohin der Übergang vom Zustand ⟨q₀, p₀⟩ bei der Eingabe 0 führt. Wir stellen fest, wohin der Übergang vom Zustand q₀ bei der Eingabe 0 im Automaten A₁ führt: Er führt in den Zustand q₁. Im Automaten A₂ führt der Übergang von p₀ bei der Null in den Zustand p₁. In die Tabelle schreiben wir also ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Bei der Eingabe 1 erhalten wir: Für den Automaten A₁ gilt δ₁(q₀, 1) = q₂ und für den Automaten A₂ gilt δ₂(p₀, 1) = p₀. Wir erhalten also den Zustand ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Wir ergänzen den Rest der Tabelle:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

Und anhand dieser Tabelle zeichnen wir nur noch den Rest des Diagramms.

Wir können ausprobieren, ob der Automat so funktioniert, wie er soll. Wir versuchen, das Wort 0100 zu akzeptieren. Der Automat durchläuft nacheinander die Zustände

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Da der Zustand ⟨q₂, p₁⟩ ein Endzustand ist, akzeptiert der Automat A das Wort 0100. Wie würde es ausgehen, wenn wir versuchten, das Wort 0100 mit den Automaten A₁ und A₂ zu akzeptieren? Der Automat A₁ würde nacheinander diese Zustände durchlaufen:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

Der Automat endete im Zustand q₂, der kein Endzustand ist, also würde der Automat A₁ dieses Wort nicht akzeptieren. Und der Automat A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

Der Zustand p₁ ist ein Endzustand, also würde der Automat A₂ das Wort 0100 akzeptieren. Beachte, dass die Automaten A₁ und A₂ in den Zuständen q₂ und p₁ endeten, was damit übereinstimmt, dass der Automat A im Zustand ⟨q₂, p₁⟩ endete.

Vorgehen mit einem nichtdeterministischen Automaten

Beispiel

Dass die Menge der regulären Sprachen unter der Vereinigung abgeschlossen ist, können wir auch beweisen, indem wir einen nichtdeterministischen Automaten konstruieren, der viel einfacher sein wird.

Wir haben also zwei reguläre Sprachen L₁, L₂ und wollen beweisen, dass ihre Vereinigung L = L₁ ∪ L₂ ebenfalls eine reguläre Sprache ist. Da L₁, L₂ reguläre Sprachen sind, muss es Automaten A₁, A₂ geben, die diese Sprachen akzeptieren. D. h. es gilt L(A₁) = L₁ und L(A₂) = L₂. Mithilfe dieser Automaten konstruieren wir den Automaten A, der die Sprache L akzeptiert, d. h. L(A) = L.

Nehmen wir an, die endlichen Automaten A₁ und A₂ sehen so aus:

und

Den Automaten, der die Vereinigung beider Sprachen akzeptiert, konstruieren wir so, dass wir einen neuen Startzustand erzeugen und von diesem Zustand zwei ε-Übergänge zu den ursprünglichen Startzuständen führen. Das ist alles. Der Automat sähe so aus:

Formalisierung

Wir haben zwei Automaten A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ und A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Wir konstruieren den Automaten A = ⟨Q, Σ, δ, q₀, F⟩, der die Vereinigung der Sprachen akzeptiert, die von den vorherigen Automaten akzeptiert werden, d. h. L(A) = L(A₁) ∪ L(A₂). Dabei gilt:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

Und die Übergangsfunktion δ definieren wir so:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & falls & q \in Q_{1} \\ δ_{2} (q, a) & falls & q \in Q_{2} \\ {q_{1}, q_{2}} & falls & q = q_{0} \land a = ε \\ \emptyset & falls & q = q_{0} \land a \neq ε \end{cases}$

Quellen

Kapitel: Abgeschlossenheit regulärer Sprachen, Vereinigung regulärer Sprachen, Schnitt regulärer Sprachen, Differenz regulärer Sprachen, Komplement einer regulären Sprache, Konkatenation regulärer Sprachen, Kleene-Stern einer regulären Sprache

« Zurück: Abgeschlossenheit regulärer Sprachen

Weiter: Schnitt regulärer Sprachen »