Concatenarea limbajelor regulate

Fie două limbaje regulate L₁, L₂. Vom demonstra că concatenarea lor L = L₁ ∘ L₂ este, de asemenea, un limbaj regulat.

Ce este concatenarea

Prin concatenarea cuvintelor „010” și „1111” obținem cuvântul „0101111”. Concatenarea limbajelor creează deci un limbaj nou, pe care îl construim concatenând fiecare cuvânt dintr-un limbaj cu fiecare cuvânt din celălalt limbaj. Concatenarea a două cuvinte și a două limbaje o vom nota cu un cerculeț: ∘. Putem defini atunci concatenarea limbajelor L₁ și L₂ astfel:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Ideea demonstrației

Avem două limbaje regulate L₁, L₂ și două automate care acceptă aceste limbaje:

$$\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 un automat nedeterminist A = ⟨Q, Σ, δ, q, F⟩ care va „conține în sine” ambele automate A₁ și A₂. Ideea de bază este că începem să acceptăm cuvântul cu automatul A₁ și, când automatul A₁ ajunge într-o stare finală, încercăm să acceptăm restul cuvântului cu automatul A₂. Dacă și acest automat acceptă partea respectivă a cuvântului, atunci automatul A acceptă cuvântul.

Exemplu

Fie automatul A₁, care acceptă cuvintele nevide formate numai din zerouri și cuvintele formate dintr-o unitate urmată numai de zerouri (1, 10, 100, …):

și automatul A₂, care acceptă cuvintele ce se termină cu 01:

Unim automatele astfel: din toate stările finale ale automatului A₁ adăugăm ε-tranziții în starea inițială a automatului A₂, apoi transformăm stările finale ale lui A₁ în stări obișnuite. Starea inițială a întregului automat nou va fi starea inițială a automatului A₁:

Cum va funcționa automatul? Începem să simulăm funcționarea automatului A₁. Dacă trecem într-una dintre fostele stări finale q₁ sau q₂, știm că automatul A₁ acceptă o parte din cuvânt. Pentru ca întregul cuvânt să facă parte din limbajul L₁ ∘ L₂, restul cuvântului trebuie acceptat de al doilea automat A₂ – de aceea, din toate fostele stări finale pornesc ε-tranziții în starea inițială originală a automatului A₂.

Să luăm ca exemplu cuvântul 0001. El aparține concatenării celor două limbaje, deoarece cuvântul poate fi obținut prin concatenarea cuvintelor 00 ∘ 01. Dar la fel de bine poate fi obținut prin concatenarea cuvintelor 0 ∘ 001. În automatul nostru putem simula ambele variante. Automatul poate urma drumul:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Pe acest drum, automatul ar „accepta” mai întâi partea 00 a cuvântului, apoi partea 01. Sau poate urma drumul:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

iar automatul ar „accepta” astfel mai întâi partea 0 a cuvântului, apoi partea 001. În ambele cazuri ajungem, desigur, în starea finală p₂.

Construcția formală

Încă o dată: avem două limbaje regulate L₁, L₂ și două automate care acceptă aceste limbaje:

$$\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 un automat nedeterminist A = ⟨Q, Σ, δ, q, F⟩ pentru care are loc:

• Q = Q₁ ∪ Q₂ (presupunem totodată că Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Funcția de tranziție δ o construim pe rând:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{dacă}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{dacă}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{dacă}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{dacă}& q\in Q_2\end{array}$$

Surse

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