Różnica języków regularnych
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ść:
gdzie L2′ 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 L1 ∩ L2′, 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 A2′, 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(A2′):
Źródła
Rozdziały: Domkniętość języków regularnych, Suma, Przecięcie, Różnica, Dopełnienie, Konkatenacja, Domknięcie Kleene’ego