✖

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

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

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ść:

∀q∈Q1,p∈Q2:δ(⟨q,p⟩,a)=⟨δ1(q,a),δ2(p,a)⟩

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