Przecięcie języków regularnych
Kapitoly: Zamykanie języków regularnych, Unifikacja, Dostęp, Różnica, Uzupełnienie, Konkatenacja, Wnioski
Mamy dwa języki regularne L1, L2. Udowodnimy, że ich przecięcie L = L1 ∩ L2 jest również językiem regularnym.
Idea dowodu
Biorąc pod uwagę dwa języki regularne L1 i L2, chcemy udowodnić, że ich przecięcie L1 ∩ L2 jest również językiem regularnym. Ponieważ L1 i L2 są językami regularnymi, istnieją skończone automaty A1 i A2, które akceptują języki L1 i L2, więc L(A1) = L1 i L(A2) = L2 zachodzą. Następnie konstruujemy skończony automat A, który akceptuje język L1 ∩ L2, dowodząc, że język L1 ∩ L2 jest regularny.
Słowo należy do przecięcia języków, jeśli należy do języka L1 oraz L2. Zatem słowo musi być akceptowane przez automat A1 oraz przez automat A2. Użyjemy dokładnie tego samego pomysłu, co w przypadku unifikacji języków regularnych, tylko zmienimy zbiór stanów skończonych.
Formalizacja procedury.
Mamy dwa automaty,
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}
Konstruujemy automat $A=\left<Q, \Sigma, \delta, q, F\right>$, który akceptuje język L(A1)∩ L(A2). Zachodzi następująca zależność
- Q = Q1 × Q2
- $\Sigma = \Sigma_1 \cap \Sigma_2$
- q = <q0, p0>
- F = F1 × F2
Dla funkcji przejścia δ zachodzi następująca zależność:
$$ \forall q\in Q_1, p\in Q_2: \delta(\left<q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right> $$
Przykład
Rozważmy automat A1, który akceptuje wszystkie słowa zawierające parzystą liczbę 1:
oraz automat A2, który akceptuje słowa zawierające nieparzystą liczbę 0:
Skonstruuj automat, który akceptuje przecięcie tych języków. Zbiór stanów tego automatu ma postać Q = Q1 × Q2, stan początkowy to <q0, p0>, a stany końcowe to F1 × F2:
Następnie uzupełniamy przejścia tak, aby δ(<q,p>, a) = <δ1(q, a), δ2(p, a)>:
Na przykład, w tym automacie, stan <q0, p0> jest przejściem dla symbolu 0 do stanu <q0,p1>. Oznacza to, że automat A1 ma przejście dla symbolu 0 ze stanu q0 z powrotem do stanu q0. Automat A2 ma z kolei przejście dla symbolu 0 ze stanu p0 do stanu p1.
Możemy przetestować automat. Powinien on akceptować słowa takie jak 110 lub 00000 (zawierają one parzystą liczbę jedynek i nieparzystą liczbę zer), ale nie powinien akceptować słów takich jak 11, 111, 1010).