Doorsnede van reguliere talen

Neem twee reguliere talen L₁, L₂. We bewijzen dat hun doorsnede L = L₁ ∩ L₂ ook een reguliere taal is.

Idee van het bewijs

We hebben twee reguliere talen L₁ en L₂ en willen bewijzen dat hun doorsnede L₁ ∩ L₂ weer een reguliere taal is. Omdat L₁ en L₂ reguliere talen zijn, bestaan er eindige automaten A₁ en A₂ die de talen L₁ en L₂ accepteren, dus er geldt L(A₁) = L₁ en L(A₂) = L₂. We construeren vervolgens een eindige automaat A die de taal L₁ ∩ L₂ accepteert, waarmee we bewijzen dat de taal L₁ ∩ L₂ regulier is.

Een woord behoort tot de doorsnede van talen als het tot de taal L₁ en tegelijk tot L₂ behoort. Het woord moet dus door automaat A₁ en tegelijk door automaat A₂ worden geaccepteerd. We gebruiken precies hetzelfde idee als bij de vereniging van reguliere talen, alleen veranderen we de verzameling eindtoestanden.

Formalisering van de werkwijze

We hebben twee 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}$$

We construeren een automaat A = ⟨Q, Σ, δ, q, F⟩ die de taal L(A₁) ∩ L(A₂) accepteert. Er geldt dat

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

Voor de overgangsfunctie δ geldt de volgende betrekking:

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

Voorbeeld

Neem deze automaat A₁, die alle woorden accepteert die een even aantal enen bevatten:

en automaat A₂, die woorden accepteert die een oneven aantal nullen bevatten:

We construeren een automaat die de doorsnede van deze talen accepteert. De verzameling toestanden van deze automaat is Q = Q₁ × Q₂, de begintoestand is toestand ⟨q₀, p₀⟩ en de eindtoestanden zijn F₁ × F₂:

Vervolgens maken we de overgangen af zodat δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

In deze automaat loopt bijvoorbeeld vanuit toestand ⟨q₀, p₀⟩ een overgang voor het symbool 0 naar toestand ⟨q₀,p₁⟩. Dat betekent dat automaat A₁ vanuit toestand q₀ een overgang voor het symbool 0 terug naar toestand q₀ heeft. Automaat A₂ heeft voor het symbool 0 weer een overgang van toestand p₀ naar toestand p₁.

We kunnen de automaat uitproberen. Hij zou woorden moeten accepteren als 110 of 00000 (die bevatten een even aantal enen en tegelijk een oneven aantal nullen), maar niet woorden als 11, 111, 1010.

Bronnen

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