✖

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

L1∖L2=L1∩L2′,

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