Dopełnienie języka regularnego
Kapitoly: Domkniętość języków regularnych, Suma, Przecięcie, Różnica, Dopełnienie, Konkatenacja, Domknięcie Kleene’ego
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 $\Sigma$ zachodzi:
$$ 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, 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=\left<Q, \Sigma, \delta, q_0, F\right>$, 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'=\left<Q, \Sigma, \delta, q_0, Q\setminus F\right>$. To wszystko.
Przykład
Weźmy taki automat:
Automat akceptujący dopełnienie języka wyglądałby tak:
