Unifikacja języków regularnych

Kapitoly: Zamykanie języków regularnych, Unifikacja, Dostęp, Różnica, Uzupełnienie, Konkatenacja, Wnioski

Mamy dwa języki regularne L₁, L₂. Udowodnimy, że ich związek L = L₁ ∪ L₂ jest również językiem regularnym.

Procedura wykorzystująca automat deterministyczny

Idea procedury

Mamy dwa języki regularne L₁ i L₂ i chcemy udowodnić, że ich związek L₁ ∪ L₂ jest również językiem regularnym. Ponieważ L₁ i L₂ są językami regularnymi, istnieją skończone automaty A₁ i A₂, które akceptują języki L₁ i L₂, więc L(A₁) = L₁ i L(A₂) = L₂ są poprawne. Następnie konstruujemy skończony automat A, który zaakceptuje język L₁ ∪ L₂, udowadniając, że język L₁ ∪ L₂ jest regularny.

Jak to zrobić? Mamy pod ręką skończone automaty A₁ i A₂, które akceptują każdy język. Możemy powiedzieć, że słowo w należy do języka L₁ ∪ L₂ wtedy i tylko wtedy, gdy jest akceptowane przez co najmniej jeden z automatów A₁ lub A₂.

Automat A może działać poprzez symulację obliczeń automatu A₁ dla danych wejściowych w dla danych wejściowych w. Jeśli A₁ zaakceptuje słowo w, to w również zaakceptuje A. Jeśli A₁ odrzuci słowo w, to A nadal będzie próbował symulować obliczenia A₂ dla wejścia w. Jeśli A₂ zaakceptuje słowo w, wówczas A również zaakceptuje słowo w. W przeciwnym razie odrzuci je.

Pozostaje nam sformalizować, co to znaczy, że automat A "symuluje" obliczenia innego automatu.

Formalizacja

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

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

Skonstruujemy skończony automat $A=\left<Q, \Sigma, \delta, q, F\right>$, który będzie akceptował język L = L₁∪ L₂. Wykorzystamy ideę symulacji dwóch automatów A₁, A₂. Wyobraźmy sobie więc, że mamy słowo w = w₁w₂… w_n jako dane wejściowe, a teraz będzie on symulował postęp automatów A₁ i A₂ jednocześnie 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>. Wykonamy teraz krok obliczeniowy w każdym automacie, aby uzyskać konfiguracje <δ₁(q₁, w₁), w₂… w_n> i <δ₂(q₂, w₁), w₂… w_n>.

Widzimy, że te konfiguracje różnią się tylko pierwszym komponentem, drugi - nieprzeczytana część słowa - jest zawsze taki sam. Tak więc nie musimy utrzymywać dwóch konfiguracji dwóch automatów podczas symulacji, ale potrzebujemy tylko jednej konfiguracji postaci <<q_i, q_j>, w_l… w_n>, gdzie q_i ∈ Q₁ i q_j ∈ Q₂. Innymi słowy, nasz skompilowany automat A będzie miał początkową konfigurację <<q₁, q₂>, w>. Pierwsza część pary <q₁, q₂> reprezentuje stan, w którym aktualnie znajduje się automat A₁, a druga część reprezentuje aktualny stan automatu A₂.

Możemy zatem napisać, że kompilowany automat A będzie miał zbiór stanów równy Q = Q₁ × Q₂. Będzie to iloczyn kartezjański stanów z poprzednich dwóch automatów. Następująca idea jest taka, że automat A będzie miał stan początkowy <q₁, q₂> i jeśli automat A₁ przejdzie do stanu q_i dla symbolu w₁ i automat A₂ przejdzie do stanu q_j dla symbolu w₁, to automat A przejdzie do stanu <q_i, q_j> dla symbolu w₁.

Funkcję przejścia δ zapisujemy w następujący sposób (tutaj zakładamy, że aktualnie znajdujemy się 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> $$

Do uporządkowania pozostały już tylko drobne rzeczy. Dla alfabetu, $\Sigma = \Sigma_1 \cup \Sigma_2$. Stan początkowy jest równy q = <q₁, q₂>. A stany końcowe to wszystkie pary <q_i, q_j> takie, że albo q_i ∈ F₁ albo q_j ∈ F₂.

Ilustracja procedury

Weźmy dwa automaty. Pierwszym z nich jest automat A₁, który akceptuje wszystkie słowa (w tym słowo puste), w których zera i jedynki występują naprzemiennie, tj. słowa postaci 01, 0101, 010101, ....

Drugi automat A₂ akceptuje słowa zawierające co najmniej jedno zero:

Unifikacja tych języków to słowa, które albo zawierają zero, albo są postaci 01, 0101, ... Skonstruujemy teraz ostateczny automat $A=\left<Q, \Sigma, \delta, q, F\right>$, który zaakceptuje ten zunifikowany język. Najpierw pokażemy, jak będą wyglądać stany tego nowego automatu A. Będzie to iloczyn kartezjański 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 na diagramie wyglądałoby sześć stanów automatu A, który akceptuje zunifikowany język L(A₁) ∪ L(A₂):

Nie przejmuj się, że istnieją stany, które składają się z par stanów - to tylko po to, aby dać ci lepsze wyobrażenie o tym, co faktycznie dzieje się w automacie. Stany można łatwo nazwać klasycznie q₀, …, q₅. Stany końcowe to te stany, które zawierają stan q₀ lub p₁, które są stanami końcowymi oryginalnego automatu. Stan początkowy to <p₀, q₀>.

Teraz musimy znaleźć wszystkie przejścia. Napiszmy 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} $$

Tabelę będziemy uzupełniać na bieżąco. Pierwszą rzeczą, jaką zrobimy, jest znalezienie miejsca, do którego prowadzi przejście ze stanu <q₀, p₀> po wpisaniu 0. Dowiemy się, gdzie prowadzi przejście ze stanu q₀ po wpisaniu 0 w automacie A₁: prowadzi to do stanu q₁. W automacie A₂ przejście ze stanu p₀ na zero prowadzi do stanu p₁. W tabeli zapisujemy 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} $$

Na wejściu 1 otrzymujemy: dla automatu A₁ mamy δ₁(q₀, 1) = q₂, a dla automatu A₂ mamy δ₂(p₀, 1) = p₀. Otrzymujemy 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} $$

Uzupełnijmy 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 zgodnie z tą tabelą narysujemy resztę diagramu.

Możemy przetestować, czy automat działa tak, jak powinien. Spróbujmy zaakceptować słowo 0100. Automat przejdzie przez kolejne 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 końcowym, automat A akceptuje słowo 0100. Jak by to działało, gdybyśmy spróbowali zaakceptować słowo 0100 za pomocą automatów A₁ i A₂? Automat A₁ przechodziłby przez te stany sekwencyjnie:

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

Automat skończył w stanie q₂, który nie jest stanem końcowym, więc automat A₁ nie zaakceptowałby tego słowa. A co z automatem A₂?

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

Stan p₁ jest stanem końcowym, więc automat A₂ zaakceptowałby słowo 0100. Zauważ, że automaty A₁ i A₂ znalazły się w stanach q₂ i p₁, co jest zgodne z automatem A znajdującym się w stanie <q₂, p₁>.

Procedura wykorzystująca automat niedeterministyczny

Przykład

Możemy udowodnić, że zbiór języków regularnych jest zamknięty w unii poprzez skonstruowanie niedeterministycznego automatu, co będzie znacznie prostsze.

Mamy więc dwa języki regularne L₁, L₂ i chcemy udowodnić, że ich unia L = L₁ ∪ L₂ jest również językiem regularnym. Ponieważ L₁, L₂ są językami regularnymi, muszą istnieć automaty A₁, A₂ akceptujące te języki. Są to L(A₁) = L₁ i L(A₂) = L₂. Używając tych automatów, skonstruujemy automat A akceptujący język L, czyli L(A) = L.

Załóżmy, że końcowe automaty A₁ i A₂ wyglądają następująco:

Skonstruowalibyśmy automat, który akceptuje połączenie tych dwóch języków, tworząc nowy stan początkowy i prowadząc dwa przejścia epsilon z tego stanu do oryginalnych 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>$. Konstruujemy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, który będzie akceptował unię języków akceptowanych przez poprzednie automaty, tj. L(A) = L(A₁)∪ L(A₂). W ten sposób:

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

Definiujemy funkcję przejścia δ w następujący sposób:

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

Zasoby

« Poprzedni: Zamykanie języków regularnych

Dalszy: Dostęp »