Complementul unui limbaj regulat

Fie un limbaj regulat L. Vom demonstra că complementul limbajului L este tot un limbaj regulat.

Ce este complementul

Prin complementul limbajului L înțelegem toate cuvintele care nu aparțin limbajului L. Complementul se notează L'. Adică, pentru alfabetul Σ avem:

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

De exemplu, pentru limbajul cuvintelor care conțin cel puțin un simbol 1, complementul ar fi limbajul format din cuvintele care nu conțin niciun simbol 1.

Construcția

Construcția este foarte simplă. Avem un limbaj regulat L și un automat complet determinist A = ⟨Q, Σ, δ, q₀, F⟩ care îl acceptă (orice automat finit poate fi transformat într-unul de acest fel). Automatul A', care acceptă L', îl construim interschimbând stările finale cu cele nefinale: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Asta e tot.

Exemplu

Fie acest automat:

Automatul care acceptă complementul limbajului ar arăta astfel:

Surse

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