✖

Dopełnienie języka regularnego

Mamy język regularny L. Udowodnimy, że dopełnienie języka L jest znowu językiem regularnym.

Co to jest dopełnienie

Przez dopełnienie języka L rozumiemy zbiór wszystkich słów, które nie należą do języka L. Dopełnienie oznaczamy L'. Czyli dla alfabetu Σ zachodzi:

L′={w∈Σ∗|w∉L}.

Na przykład dla języka słów zawierających co najmniej jeden symbol 1 dopełnieniem byłby język, który zawiera słowa niezawierające ani jednego symbolu 1.

Konstrukcja

Konstrukcja jest bardzo prosta. Mamy język regularny L i deterministyczny automat zupełny A = ⟨Q, Σ, δ, q0, F⟩, który go akceptuje (każdy automat skończony da się na taki przekształcić). Automat A', który akceptuje L', zbudujemy tak, że zamienimy stany akceptujące i nieakceptujące: A' = ⟨Q, Σ, δ, q0, Q ∖ F⟩. To wszystko.

Przykład

Weźmy taki automat:

Automat akceptujący dopełnienie języka wyglądałby tak:

Źródła

Rozdziały: Domkniętość języków regularnych, Suma, Przecięcie, Różnica, Dopełnienie, Konkatenacja, Domknięcie Kleene’ego