Suma języków regularnych

Weźmy dwa języki regularne L₁, L₂. Udowodnimy, że ich suma L = L₁ ∪ L₂ też jest językiem regularnym.

Konstrukcja za pomocą automatu deterministycznego

Główna idea

Mamy dwa języki regularne L₁ i L₂ i chcemy udowodnić, że ich suma L₁ ∪ L₂ jest znowu językiem regularnym. Ponieważ L₁ i L₂ są językami regularnymi, istnieją automaty skończone A₁ i A₂, które akceptują języki L₁ i L₂, czyli zachodzi L(A₁) = L₁ i L(A₂) = L₂. Dalej zbudujemy automat skończony A, który będzie akceptował język L₁ ∪ L₂, i w ten sposób udowodnimy, że język L₁ ∪ L₂ jest regularny.

Jak to zrobimy? Mamy pod ręką automaty skończone A₁ i A₂, które akceptują poszczególne języki. Możemy powiedzieć, że słowo w należy do języka L₁ ∪ L₂ wtedy i tylko wtedy, gdy akceptuje je co najmniej jeden z automatów A₁ i A₂.

Automat A mógłby działać tak, że dla wejścia w będzie symulował obliczenie automatu A₁ dla wejścia w. Jeśli A₁ zaakceptuje słowo w, to słowo w zaakceptuje też A. Jeśli A₁ odrzuci słowo w, to A spróbuje jeszcze zasymulować obliczenie A₂ dla wejścia w. Jeśli A₂ zaakceptuje słowo w, to A też zaakceptuje słowo w. W przeciwnym razie je odrzuci.

Zostaje nam sformalizować, co to znaczy, że automat A „symuluje” obliczenie innego automatu.

Formalizacja

Mamy dwa języki regularne L₁ i L₂, które są akceptowane przez automaty skończone

\begin{eqnarray} A_1 &=& \left<Q_1, \Sigma_1, \delta_1, q_1, F_1\right>\\ A_2 &=& \left<Q_2, \Sigma_2, \delta_2, q_2, F_2\right>. \end{eqnarray}

Zbudujemy automat skończony $A=\left<Q, \Sigma, \delta, q, F\right>$, który będzie akceptował język L = L₁∪ L₂. Wykorzystamy ideę symulowania dwóch automatów A₁, A₂. Wyobraźmy sobie, że na wejściu mamy słowo w = w₁w₂… w_n i teraz będziemy jednocześnie symulować przebieg automatów A₁ i A₂ dla słowa w. Konfiguracja początkowa automatu A₁ to <q₁, w₁w₂… w_n>, konfiguracja początkowa A₂ to <q₂, w₁w₂… w_n>. W każdym automacie wykonamy teraz krok obliczenia i w ten sposób dostaniemy się do konfiguracji <δ₁(q₁, w₁), w₂… w_n> i <δ₂(q₂, w₁), w₂… w_n>.

Widzimy, że te konfiguracje różnią się tylko pierwszą składową, drugą – nieprzeczytaną część słowa – mają zawsze taką samą. Podczas symulacji nie musimy więc przechowywać dwóch konfiguracji dwóch automatów, wystarczy nam jedna konfiguracja postaci <<q_i, q_j>, w_l… w_n>, gdzie q_i ∈ Q₁ i q_j ∈ Q₂. Innymi słowy, budowany automat A będzie miał konfigurację początkową <<q₁, q₂>, w>. Pierwsza część pary <q₁, q₂> przedstawia stan, w którym aktualnie znajduje się automat A₁, a druga składowa przedstawia aktualny stan automatu A₂.

Możemy więc napisać, że budowany automat A będzie miał zbiór stanów równy Q = Q₁ × Q₂. Będzie to iloczyn kartezjański zbiorów stanów obu poprzednich automatów. Dalej idea jest taka, że automat A będzie miał stan początkowy <q₁, q₂>, a jeśli automat A₁ przejdzie dla symbolu w₁ do stanu q_i, a automat A₂ przejdzie dla symbolu w₁ do stanu q_j, to automat A przejdzie dla symbolu w₁ do stanu <q_i, q_j>.

Funkcję przejścia δ zapiszemy tak (tutaj już zakładamy, że jesteśmy aktualnie w stanach q_i i q_j):

$$ \delta\left(\left<q_i, q_j\right>,w\right) = \left<\delta_1(q_i,w), \delta_2(q_j,w)\right> $$

Zostają już tylko drobiazgi. Dla alfabetu zachodzi $\Sigma = \Sigma_1 \cup \Sigma_2$. Stan początkowy jest równy q = <q₁, q₂>. A stanami akceptującymi są wszystkie pary <q_i, q_j> takie, że q_i ∈ F₁ albo q_j ∈ F₂.

Ilustracja konstrukcji

Weźmy dwa automaty. Pierwszy to automat A₁, który akceptuje wszystkie słowa (łącznie ze słowem pustym), w których przeplatają się zera i jedynki, czyli słowa postaci 01, 0101, 010101, …

Drugi automat A₂ akceptuje słowa, które zawierają co najmniej jedno zero:

Sumą tych języków są słowa, które albo zawierają zero, albo są postaci 01, 0101, … Teraz zbudujemy automat skończony $A=\left<Q, \Sigma, \delta, q, F\right>$, który będzie akceptował właśnie tę sumę języków. Najpierw pokażemy, jak będą wyglądać stany tego nowego automatu A. Będzie to iloczyn kartezjański zbiorów stanów pierwszego i drugiego automatu:

$$ Q = Q_1 \times Q_2 = \left\{\left<q_0, p_0\right>, \left<q_0, p_1\right>, \left<q_1, p_0\right>, \left<q_1, p_1\right>, \left<q_2, p_0\right>, \left<q_2, p_1\right>\right\} $$

Tak wygląda sześć stanów automatu A, który akceptuje sumę języków L(A₁) ∪ L(A₂). Na diagramie wyglądałyby tak:

Nie przestrasz się, że mamy tu stany złożone z par stanów – służy to tylko do lepszej orientacji w tym, co się właściwie w automacie dzieje. Stany mogłyby się spokojnie nazywać klasycznie q₀, …, q₅. Stany akceptujące to te stany, które zawierają stan q₀ albo p₁, czyli stany akceptujące pierwotnych automatów. Stan początkowy to <q₀, p₀>.

Teraz musimy znaleźć wszystkie przejścia. Zapiszemy sobie taką tabelę:

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$

I stopniowo będziemy ją uzupełniać. Najpierw sprawdzimy, dokąd prowadzi przejście ze stanu <q₀, p₀> dla wejścia 0. Sprawdzimy, dokąd prowadzi przejście ze stanu q₀ dla wejścia 0 w automacie A₁: prowadzi do stanu q₁. W automacie A₂ przejście z p₀ dla zera prowadzi do stanu p₁. Do tabeli wpiszemy więc <q₁, p₁>:

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$

Dla wejścia 1 dostaniemy: dla automatu A₁ mamy δ₁(q₀, 1) = q₂, a dla automatu A₂ mamy δ₂(p₀, 1) = p₀. Otrzymujemy więc stan <q₂, p₀>.

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>&\left<q_2, p_0\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$

Dopiszemy resztę tabeli:

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>&\left<q_2, p_0\right>\\ \left<q_0, p_1\right>&\left<q_1, p_1\right>&\left<q_2, p_1\right>\\ \left<q_1, p_0\right>&\left<q_2, p_1\right>&\left<q_0, p_0\right>\\ \left<q_1, p_1\right>&\left<q_2, p_1\right>&\left<q_0, p_1\right>\\ \left<q_2, p_0\right>&\left<q_2,p_1\right>&\left<q_2, p_0\right>\\ \left<q_2, p_1\right>&\left<q_2,p_1\right>&\left<q_2,p_1\right>\\ \end{array} $$

I według tej tabeli już tylko dorysujemy resztę diagramu.

Możemy sprawdzić, że automat działa, jak powinien. Spróbujemy zaakceptować słowo 0100. Automat po kolei przejdzie przez stany

$$ \left<q_0, p_0\right>, \left<q_1, p_1\right>, \left<q_0, p_1\right>, \left<q_1, p_1\right>, \left<q_2, p_1\right> $$

Ponieważ stan <q₂, p₁> jest stanem akceptującym, automat A akceptuje słowo 0100. Jak by to wyglądało, gdybyśmy spróbowali zaakceptować słowo 0100 automatami A₁ i A₂? Automat A₁ przeszedłby po kolei przez takie stany:

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

Automat skończył w stanie q₂, który nie jest akceptujący, więc automat A₁ tego słowa by nie zaakceptował. A automat A₂?

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

Stan p₁ jest akceptujący, więc automat A₂ słowo 0100 by zaakceptował. Zauważ, że automaty A₁ i A₂ skończyły w stanach q₂ i p₁, co zgadza się z tym, że automat A skończył w stanie <q₂, p₁>.

Konstrukcja za pomocą automatu niedeterministycznego

Przykład

To, że zbiór języków regularnych jest domknięty ze względu na sumę, możemy udowodnić także, budując automat niedeterministyczny, co będzie dużo prostsze.

Mamy więc dwa języki regularne L₁, L₂ i chcemy udowodnić, że ich suma L = L₁ ∪ L₂ też jest językiem regularnym. Ponieważ L₁, L₂ są językami regularnymi, muszą istnieć automaty A₁, A₂, które te języki akceptują. Czyli zachodzi L(A₁) = L₁ i L(A₂) = L₂. Za pomocą tych automatów zbudujemy automat A, który będzie akceptował język L, czyli L(A) = L.

Załóżmy, że automaty skończone A₁ i A₂ wyglądają tak:

i

Automat, który akceptowałby sumę obu języków, zbudowalibyśmy tak, że utworzylibyśmy nowy stan początkowy i z tego stanu poprowadzilibyśmy dwa epsilon-przejścia do pierwotnych stanów początkowych. To wszystko. Automat wyglądałby tak:

Formalizacja

Mamy dwa automaty $A_1=\left<Q_1, \Sigma, \delta_1, q_1, F_1\right>$ i $A_2=\left<Q_2, \Sigma, \delta_2, q_2, F_2\right>$. Zbudujemy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, który będzie akceptował sumę języków akceptowanych przez poprzednie automaty, czyli L(A) = L(A₁)∪ L(A₂). Przy tym zachodzi:

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

A funkcję przejścia δ definiujemy tak:

$$ \delta(q,a)= \begin{cases} \delta_1(q,a)&\mbox{jeśli}&q\in Q_1\\ \delta_2(q,a)&\mbox{jeśli}&q\in Q_2\\ \left\{q_1, q_2\right\}&\mbox{jeśli}&q=q_0 \wedge a=\varepsilon\\ \emptyset&\mbox{jeśli}&q=q_0\wedge a\ne\varepsilon \end{cases} $$

Źródła

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