Snitt av regulære språk

La oss ha to regulære språk L₁, L₂. Vi skal bevise at snittet L = L₁ ∩ L₂ også er et regulært språk.

Ideen bak beviset

Vi har to regulære språk L₁ og L₂, og vi vil bevise at snittet L₁ ∩ L₂ igjen er et regulært språk. Siden L₁ og L₂ er regulære språk, finnes det endelige automater A₁ og A₂ som aksepterer språkene L₁ og L₂, altså gjelder L(A₁) = L₁ og L(A₂) = L₂. Vi konstruerer så en endelig automat A som aksepterer språket L₁ ∩ L₂, og dermed beviser vi at språket L₁ ∩ L₂ er regulært.

Et ord tilhører snittet av språkene hvis det tilhører språket L₁ og samtidig L₂. Altså må ordet aksepteres av automaten A₁ og samtidig av automaten A₂. Vi bruker nøyaktig den samme ideen som vi brukte for union av regulære språk, vi endrer bare mengden av sluttilstander.

Formalisering av framgangsmåten

Vi har to automater,

$$\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}$$

Vi konstruerer automaten A = ⟨Q, Σ, δ, q, F⟩ som aksepterer språket L(A₁) ∩ L(A₂). Det gjelder at

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

For overgangsfunksjonen δ vil denne sammenhengen gjelde:

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

Eksempel

La oss ha denne automaten A₁, som aksepterer alle ord som inneholder et like antall enere:

og automaten A₂, som aksepterer ord som inneholder et odde antall nuller:

Vi konstruerer en automat som skal akseptere snittet av disse språkene. Mengden av tilstander i denne automaten har formen Q = Q₁ × Q₂, starttilstanden er tilstanden ⟨q₀, p₀⟩, og sluttilstandene er F₁ × F₂:

Videre fyller vi ut overgangene slik at δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

I denne automaten går det for eksempel en overgang fra tilstanden ⟨q₀, p₀⟩ for symbolet 0 til tilstanden ⟨q₀,p₁⟩. Det betyr at automaten A₁ har en overgang fra tilstanden q₀ for symbolet 0 tilbake til tilstanden q₀. Automaten A₂ har på sin side en overgang for symbolet 0 fra tilstanden p₀ til tilstanden p₁.

Vi kan teste automaten. Den skal akseptere ord som 110 eller 00000 (de inneholder et like antall enere og samtidig et odde antall nuller), men den skal ikke akseptere ord som 11, 111, 1010.

Kilder

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