Schnitt regulärer Sprachen

Gegeben seien zwei reguläre Sprachen L₁, L₂. Wir beweisen, dass ihr Schnitt L = L₁ ∩ L₂ ebenfalls eine reguläre Sprache ist.

Idee des Beweises

Wir haben zwei reguläre Sprachen L₁ und L₂ und wollen beweisen, dass ihr Schnitt 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.

Ein Wort gehört zum Schnitt der Sprachen, wenn es sowohl zur Sprache L₁ als auch zu L₂ gehört. Das Wort muss also sowohl vom Automaten A₁ als auch vom Automaten A₂ akzeptiert werden. Wir verwenden genau dieselbe Idee wie bei der Vereinigung regulärer Sprachen, ändern nur die Menge der Endzustände.

Formalisierung des Vorgehens

Wir haben zwei Automaten,

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

Wir konstruieren den Automaten A = ⟨Q, Σ, δ, q, F⟩, der die Sprache L(A₁) ∩ L(A₂) akzeptiert. Es gilt:

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Für die Übergangsfunktion δ gilt folgende Beziehung:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Beispiel

Gegeben sei dieser Automat A₁, der alle Wörter mit einer geraden Anzahl von Einsen akzeptiert:

und der Automat A₂, der Wörter mit einer ungeraden Anzahl von Nullen akzeptiert:

Wir konstruieren den Automaten, der den Schnitt dieser Sprachen akzeptiert. Die Zustandsmenge dieses Automaten hat die Form Q = Q₁ × Q₂, der Startzustand ist der Zustand ⟨q₀, p₀⟩ und die Endzustände sind F₁ × F₂:

Nun ergänzen wir die Übergänge so, dass δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩ gilt:

In diesem Automaten führt zum Beispiel vom Zustand ⟨q₀, p₀⟩ ein Übergang für das Symbol 0 in den Zustand ⟨q₀,p₁⟩. Das bedeutet: Der Automat A₁ hat vom Zustand q₀ einen Übergang für das Symbol 0 zurück in den Zustand q₀. Der Automat A₂ hat dagegen für das Symbol 0 einen Übergang vom Zustand p₀ in den Zustand p₁.

Den Automaten können wir ausprobieren. Er sollte Wörter wie 110 oder 00000 akzeptieren (sie enthalten eine gerade Anzahl von Einsen und zugleich eine ungerade Anzahl von Nullen), aber keine Wörter wie 11, 111, 1010 akzeptieren.

Quellen

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