Reuniunea limbajelor regulate

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

Construcția cu automat determinist

Ideea construcției

Avem două limbaje regulate L₁ și L₂ și vrem să demonstrăm că reuniunea 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.

Cum procedăm? Avem automatele finite A₁ și A₂, care acceptă limbajele inițiale. Putem spune că un cuvânt w aparține limbajului L₁ ∪ L₂ dacă și numai dacă este acceptat de cel puțin unul dintre automatele A₁ sau A₂.

Automatul A ar putea funcționa astfel: pentru intrarea w va simula calculul automatului A₁ pe intrarea w. Dacă A₁ acceptă cuvântul w, atunci și A acceptă cuvântul w. Dacă A₁ respinge cuvântul w, A încearcă să simuleze și calculul lui A₂ pe intrarea w. Dacă A₂ acceptă cuvântul w, atunci și A acceptă cuvântul w. În caz contrar, îl respinge.

Ne rămâne să formalizăm ce înseamnă că automatul A „simulează” calculul altui automat.

Formalizare

Avem două limbaje regulate L₁ și L₂, acceptate de automatele finite

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

Construim un automat finit A = ⟨Q, Σ, δ, q, F⟩ care va accepta limbajul L = L₁ ∪ L₂. Ne folosim de ideea simulării simultane a două automate A₁, A₂. Să ne închipuim că avem la intrare cuvântul w = w₁w₂… w_n și că simulăm în paralel funcționarea automatelor A₁ și A₂ pe cuvântul w. Configurația inițială a automatului A₁ este ⟨q₁, w₁w₂… w_n⟩, iar cea a automatului A₂ este ⟨q₂, w₁w₂… w_n⟩. Efectuăm acum în fiecare automat câte un pas de calcul și ajungem în configurațiile ⟨δ₁(q₁, w₁), w₂… w_n⟩ și ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vedem că aceste configurații diferă doar prin prima componentă; a doua – partea necitită a cuvântului – este mereu aceeași. În timpul simulării nu trebuie deci să ținem două configurații ale celor două automate, ci ne ajunge una singură, de forma ⟨⟨q_i, q_j⟩, w_l… w_n⟩, unde q_i ∈ Q₁ și q_j ∈ Q₂. Cu alte cuvinte, automatul A pe care îl construim va avea configurația inițială ⟨⟨q₁, q₂⟩, w⟩. Prima componentă a perechii ⟨q₁, q₂⟩ reprezintă starea în care se află în acel moment automatul A₁, iar a doua componentă este starea curentă a automatului A₂.

Putem scrie așadar că automatul A va avea mulțimea stărilor Q = Q₁ × Q₂. Este produsul cartezian al stărilor celor două automate de mai sus. Ideea următoare este că automatul A va avea starea inițială ⟨q₁, q₂⟩ și, dacă automatul A₁ trece pentru simbolul w₁ în starea q_i, iar automatul A₂ trece pentru simbolul w₁ în starea q_j, atunci automatul A trece pentru simbolul w₁ în starea ⟨q_i, q_j⟩.

Funcția de tranziție δ o scriem astfel (presupunem deja că ne aflăm în stările q_i și q_j):

$$\delta (⟨q_i,q_j⟩,w)=⟨{\delta }_1(q_i,w),{\delta }_2(q_j,w)⟩$$

Rămân doar mici detalii. Pentru alfabet avem Σ= Σ₁ ∪ Σ₂. Starea inițială este q = ⟨q₁, q₂⟩. Iar stările finale sunt toate perechile ⟨q_i, q_j⟩ pentru care q_i ∈ F₁ sau q_j ∈ F₂.

Ilustrarea construcției

Fie două automate. Primul este automatul A₁, care acceptă toate cuvintele (inclusiv cuvântul vid) în care alternează zerourile și unitățile, adică cuvintele de forma 01, 0101, 010101, …

Al doilea automat, A₂, acceptă cuvintele care conțin cel puțin un zero:

Reuniunea acestor limbaje este formată din cuvintele care fie conțin un zero, fie sunt de forma 01, 0101, … Construim acum automatul finit A = ⟨Q, Σ, δ, q, F⟩ care va accepta exact acest limbaj reunit. Mai întâi vedem cum vor arăta stările noului automat A. Ele formează produsul cartezian al stărilor primului și celui de-al doilea automat:

$$Q=Q_1\times Q_2=\{⟨q_0,p_0⟩,⟨q_0,p_1⟩,⟨q_1,p_0⟩,⟨q_1,p_1⟩,⟨q_2,p_0⟩,⟨q_2,p_1⟩\}$$

Acestea sunt cele șase stări ale automatului A, care acceptă limbajul reunit L(A₁) ∪ L(A₂). În diagramă ar arăta astfel:

Nu te speria că stările sunt formate din perechi de stări – așa ne orientăm mai ușor în ceea ce se petrece de fapt în automat. Stările s-ar putea numi foarte bine, ca de obicei, q₀, …, q₅. Stările finale sunt cele care conțin starea q₀ sau p₁, adică stările finale ale automatelor inițiale. Starea inițială este ⟨q₀, p₀⟩.

Acum trebuie să aflăm toate tranzițiile. Scriem un tabel:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

Și îl completăm pas cu pas. Mai întâi aflăm unde duce tranziția din starea ⟨q₀, p₀⟩ pentru intrarea 0. Vedem unde duce tranziția din starea q₀ pentru intrarea 0 în automatul A₁: duce în starea q₁. În automatul A₂, tranziția din p₀ pentru zero duce în starea p₁. În tabel scriem deci ⟨q₁, p₁⟩:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

Pentru intrarea 1 obținem: în automatul A₁ avem δ₁(q₀, 1) = q₂, iar în automatul A₂ avem δ₂(p₀, 1) = p₀. Obținem astfel starea ⟨q₂, p₀⟩.

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

Completăm restul tabelului:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_0,p_1⟩& ⟨q_1,p_1⟩& ⟨q_2,p_1⟩\\ ⟨q_1,p_0⟩& ⟨q_2,p_1⟩& ⟨q_0,p_0⟩\\ ⟨q_1,p_1⟩& ⟨q_2,p_1⟩& ⟨q_0,p_1⟩\\ ⟨q_2,p_0⟩& ⟨q_2,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩& ⟨q_2,p_1⟩& ⟨q_2,p_1⟩\end{array}$$

Iar după acest tabel desenăm restul diagramei.

Putem verifica dacă automatul funcționează cum trebuie. Încercăm să acceptăm cuvântul 0100. Automatul trece pe rând prin stările

$$⟨q_0,p_0⟩,⟨q_1,p_1⟩,⟨q_0,p_1⟩,⟨q_1,p_1⟩,⟨q_2,p_1⟩$$

Deoarece starea ⟨q₂, p₁⟩ este finală, automatul A acceptă cuvântul 0100. Cum ar fi decurs lucrurile dacă am fi încercat să acceptăm cuvântul 0100 cu automatele A₁ și A₂? Automatul A₁ ar fi trecut pe rând prin stările:

$$q_0,q_1,q_0,q_1,q_2$$

Automatul s-a oprit în starea q₂, care nu este finală, deci automatul A₁ nu ar accepta acest cuvânt. Dar automatul A₂?

$$p_0,p_1,p_1,p_1,p_1$$

Starea p₁ este finală, deci automatul A₂ ar accepta cuvântul 0100. Observă că automatele A₁ și A₂ s-au oprit în stările q₂ și p₁, ceea ce corespunde faptului că automatul A s-a oprit în starea ⟨q₂, p₁⟩.

Construcția cu automat nedeterminist

Exemplu

Faptul că mulțimea limbajelor regulate este închisă la reuniune îl putem demonstra și construind un automat nedeterminist, mult mai simplu.

Avem deci două limbaje regulate L₁, L₂ și vrem să demonstrăm că reuniunea lor L = L₁ ∪ L₂ este tot un limbaj regulat. Deoarece L₁, L₂ sunt limbaje regulate, trebuie să existe automate A₁, A₂ care acceptă aceste limbaje. Adică L(A₁) = L₁ și L(A₂) = L₂. Cu ajutorul acestor automate construim automatul A, care va accepta limbajul L, adică L(A) = L.

Presupunem că automatele finite A₁ și A₂ arată astfel:

și

Automatul care ar accepta reuniunea celor două limbaje l-am construi creând o nouă stare inițială, din care ducem două ε-tranziții în stările inițiale originale. Asta e tot. Automatul ar arăta astfel:

Formalizare

Avem două automate A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ și A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Construim automatul A = ⟨Q, Σ, δ, q₀, F⟩, care va accepta reuniunea limbajelor acceptate de automatele de mai sus, adică L(A) = L(A₁) ∪ L(A₂). Aici avem:

• Q = Q₁ ∪ Q₂ ∪ {q₀}
• F = F₁ ∪ F₂

Iar funcția de tranziție δ o definim astfel:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{dacă}& q\in Q_1\\ {\delta }_2(q,a)& \text{dacă}& q\in Q_2\\ \{q_1,q_2\}& \text{dacă}& q=q_0\wedge a=\epsilon \\ \mathrm{\varnothing }& \text{dacă}& q=q_0\wedge a\ne \epsilon \end{array}$$

Surse

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