Doplněk regulárního jazyka

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 Σ platí, že:

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

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 deterministický totální automat A = ⟨Q, Σ, δ, q₀, F⟩, který ho přijímá (každý konečný automat lze na takový převést). Automat A', který přijímá L', sestrojíme tak, že prohodíme koncové a nekoncové stavy: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. To je celé.

Příklad

Mějme tento automat:

Automat přijímající doplněk jazyka by vypadal takto:

Zdroje

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools