Różnica 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 różnica L = L1 ∖ L2 też jest językiem regularnym.
Idea
Właściwie nie ma tu wiele do udowadniania. Dla różnicy dwóch zbiorów zachodzi bowiem taka zależność:
$$ L_1 \setminus L_2 = L_1 \cap L_2^\prime, $$
gdzie $L_2^\prime$ jest dopełnieniem języka L2. Z rozdziałów o przecięciu języków regularnych i o dopełnieniu języka regularnego wiemy, że języki regularne są domknięte ze względu na obie te operacje. Oznacza to, że potrafimy zbudować automat, który akceptuje przecięcie języków, i automat, który akceptuje dopełnienie języka. Te automaty możemy więc wykorzystać do zbudowania automatu, który będzie akceptował język $L_1 \cap L_2^\prime$, a to jest przecież jednocześnie język L1 ∖ L2.
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ł różnicę tych języków. Potrzebujemy więc automatu $A_2^\prime$, który będzie akceptował dopełnienie języka automatu A2. Wystarczy zamienić stany akceptujące i nieakceptujące:
Teraz już tylko zbudujemy automat A, który będzie akceptował przecięcie języków L(A1) i $L(A_2^\prime)$:
