Doplněk regulárního jazyka
Kapitoly: Uzavřenost regulárních jazyků, Sjednocení, Průnik, Rozdíl, Doplněk, Zřetězení, Uzávěr
Máme regulární jazyk L. Dokážeme, že doplněk jazyka L je opět regulární jazyk.
Co je to doplněk
Doplňkem jazyka L rozumíme všechna slova, která nejsou v jazyku L. Doplněk značíme L' Tj. pro abecedu $\Sigma$ platí, že:
$$ L' = \left\{w \in \Sigma^\ast,|, w \notin L\right\}. $$
Například pro jazyk slov obsahujících alespoň jeden symbol 1 by doplněk byl jazyk, kter obsahuje slova, která neobsahují ani jeden symbol 1.
Postup
Postup je velice jednoduchý. Máme regulární jazyk L a automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, který ho přojímá. Automat A', který přijímá L' sestrojíme tak, že prohodíme koncové a nekoncové stavy: $A'=\left<Q, \Sigma, \delta, q_0, Q\setminus F\right>$. To je celé.
Příklad
Mějme tento automat:
Automat přijímající doplněk jazyka by vypadal takto:
