Intersecția limbajelor regulate

Fie două limbaje regulate L₁, L₂. Vom demonstra că intersecția lor L = L₁ ∩ L₂ este, de asemenea, un limbaj regulat.

Ideea demonstrației

Avem două limbaje regulate L₁ și L₂ și vrem să demonstrăm că intersecția lor L₁ ∩ L₂ este tot un limbaj regulat. Deoarece L₁ și L₂ sunt limbaje regulate, există automate finite A₁ și A₂ care acceptă limbajele L₁ și L₂, adică L(A₁) = L₁ și L(A₂) = L₂. Vom construi un automat finit A care acceptă limbajul L₁ ∩ L₂, demonstrând astfel că limbajul L₁ ∩ L₂ este regulat.

Un cuvânt aparține intersecției limbajelor dacă aparține atât limbajului L₁, cât și limbajului L₂. Așadar cuvântul trebuie să fie acceptat și de automatul A₁, și de automatul A₂. Folosim exact aceeași idee ca la reuniunea limbajelor regulate, schimbând doar mulțimea stărilor finale.

Formalizarea construcției

Avem două automate,

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

Construim automatul A = ⟨Q, Σ, δ, q, F⟩, care acceptă limbajul L(A₁) ∩ L(A₂). Avem

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

Pentru funcția de tranziție δ are loc relația:

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

Exemplu

Fie automatul A₁, care acceptă toate cuvintele ce conțin un număr par de 1:

și automatul A₂, care acceptă cuvintele ce conțin un număr impar de 0:

Construim automatul care va accepta intersecția acestor limbaje. Mulțimea stărilor acestui automat este Q = Q₁ × Q₂, starea inițială este ⟨q₀, p₀⟩, iar stările finale sunt F₁ × F₂:

Apoi completăm tranzițiile conform relației δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

În acest automat, de exemplu, din starea ⟨q₀, p₀⟩ există o tranziție pentru simbolul 0 în starea ⟨q₀,p₁⟩. Asta înseamnă că automatul A₁ are din starea q₀ o tranziție pentru simbolul 0 înapoi în starea q₀. Automatul A₂ are, la rândul lui, pentru simbolul 0 o tranziție din starea p₀ în starea p₁.

Putem încerca automatul. Ar trebui să accepte cuvinte ca 110 sau 00000 (conțin un număr par de 1 și, în același timp, un număr impar de 0), dar nu ar trebui să accepte cuvinte ca 11, 111, 1010.

Surse

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