Przecięcie języków regularnych
Kapitoly: Domkniętość języków regularnych, Suma, Przecięcie, Różnica, Dopełnienie, Konkatenacja, Domknięcie Kleene’ego
Weźmy dwa języki regularne L1, L2. Udowodnimy, że ich przecięcie (część wspólna) L = L1 ∩ L2 też jest językiem regularnym.
Idea dowodu
Mamy dwa języki regularne L1 i L2 i chcemy udowodnić, że ich przecięcie L1 ∩ L2 jest znowu językiem regularnym. Ponieważ L1 i L2 są językami regularnymi, istnieją automaty skończone A1 i A2, które akceptują języki L1 i L2, czyli zachodzi L(A1) = L1 i L(A2) = L2. Dalej zbudujemy automat skończony A, który będzie akceptował język L1 ∩ L2, i w ten sposób udowodnimy, ż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 i jednocześnie do L2. Czyli słowo musi zostać zaakceptowane zarówno przez automat A1, jak i przez automat A2. Wykorzystamy dokładnie tę samą ideę, którą wykorzystaliśmy przy sumie języków regularnych, zmienimy tylko zbiór stanów akceptujących.
Formalizacja
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}
Zbudujemy automat $A=\left<Q, \Sigma, \delta, q, F\right>$, który akceptuje język L(A1)∩ L(A2). Zachodzi
- Q = Q1 × Q2
- $\Sigma = \Sigma_1 \cap \Sigma_2$
- q = <q0, p0>
- F = F1 × F2
Dla funkcji przejścia δ będzie zachodzić taka 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
Weźmy taki automat A1, który akceptuje wszystkie słowa zawierające parzystą liczbę jedynek:
i automat A2, który akceptuje słowa zawierające nieparzystą liczbę zer:
Zbudujemy automat, który będzie akceptował przecięcie tych języków. Zbiór stanów tego automatu ma postać Q = Q1 × Q2, stanem początkowym jest stan <q0, p0>, a stanami akceptującymi są F1 × F2:
Następnie uzupełnimy przejścia tak, żeby δ(<q,p>, a) = <δ1(q, a), δ2(p, a)>:
W tym automacie na przykład ze stanu <q0, p0> prowadzi przejście dla symbolu 0 do stanu <q0,p1>. Oznacza to, że automat A1 ma ze stanu q0 przejście dla symbolu 0 z powrotem do stanu q0. Automat A2 ma z kolei dla symbolu 0 przejście ze stanu p0 do stanu p1.
Automat możesz wypróbować. Powinien akceptować słowa takie jak 110 albo 00000 (zawierają parzystą liczbę jedynek i jednocześnie nieparzystą liczbę zer), ale nie powinien akceptować słów takich jak 11, 111, 1010.