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