Przecięcie języków regularnych
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
Zbudujemy automat A = ⟨Q, Σ, δ, q, F⟩, który akceptuje język L(A1) ∩ L(A2). Zachodzi
- Q = Q1 × Q2
- Σ= Σ1 ∩ Σ2
- q = ⟨q0, p0⟩
- F = F1 × F2
Dla funkcji przejścia δ będzie zachodzić taka zależność:
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.
Źródła
Rozdziały: Domkniętość języków regularnych, Suma, Przecięcie, Różnica, Dopełnienie, Konkatenacja, Domknięcie Kleene’ego