Różnica między zwykłymi językami
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 różnica L = L1 ∖ L2 jest również językiem regularnym.
Idea
Tak naprawdę nie ma wiele do udowodnienia. W rzeczywistości dla różnicy dwóch zbiorów zachodzi następująca relacja:
$$ 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 dopełnieniu języków regularnych wiemy, że języki regularne są zamknięte na obie operacje. Oznacza to, że możemy skonstruować automat, który akceptuje przecięcie języków i dopełnienie języka. Możemy więc użyć tych automatów do skonstruowania automatu akceptującego język $L_1 \cap L_2^\prime$, który jest również językiem L1 ∖ L2.
Przykład
Załóżmy automat A1, który akceptuje wszystkie słowa zawierające parzystą liczbę jedynek:
oraz automat A2, który akceptuje słowa zawierające nieparzystą liczbę 0:
Konstruujemy automat, który akceptuje różnicę tych języków. Potrzebujemy więc automatu $A_2^\prime$, który będzie komplementarny do automatu A2. Po prostu zamieniamy stany końcowe i niekońcowe:
Teraz wystarczy skonstruować automat A, który będzie akceptował przecięcie języków L(A1) i $L(A_2^\prime)$:
