Zwykły dodatek językowy
Kapitoly: Zamykanie języków regularnych, Unifikacja, Dostęp, Różnica, Uzupełnienie, Konkatenacja, Wnioski
Mamy język regularny L. Udowodnimy, że dopełnienie L jest również językiem regularnym.
Co to jest dopełnienie
Przez dopełnienie języka L rozumiemy wszystkie słowa, których nie ma w języku L. Dopełnienie oznaczamy przez L', tzn. dla alfabetu $\Sigma$ zachodzi następująca zależność:
$$ L' = \left\{w \in \Sigma^\ast,|, w \notin L\right\}. $$
Na przykład, dla języka słów zawierających co najmniej jeden symbol 1, dopełnieniem byłby język zawierający słowa, które nie zawierają nawet jednego symbolu 1.
Procedura
Procedura jest bardzo prosta. Mamy język regularny L i automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, który go łączy. Konstruujemy automat A', który akceptuje L' poprzez zamianę stanów terminalnych i nieterminalnych: $A'=\left<Q, \Sigma, \delta, q_0, Q\setminus F\right>$. To wszystko.
Przykład
Weźmy taki automat:
Automat przyjmujący dopełnienie języka wyglądałby następująco:
