Complemento di un linguaggio regolare

Sia L un linguaggio regolare. Dimostreremo che il complemento del linguaggio L è ancora un linguaggio regolare.

Cos’è il complemento

Per complemento del linguaggio L intendiamo tutte le parole che non appartengono a L. Il complemento si indica con L'. Cioè, dato l’alfabeto Σ, si ha:

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

Ad esempio, per il linguaggio delle parole che contengono almeno un simbolo 1, il complemento è il linguaggio delle parole che non contengono nessun simbolo 1.

Procedimento

Il procedimento è molto semplice. Abbiamo un linguaggio regolare L e un automa deterministico completo A = ⟨Q, Σ, δ, q₀, F⟩ che lo accetta (ogni automa a stati finiti si può trasformare in uno di questo tipo). L’automa A' che accetta L' si costruisce scambiando gli stati finali e quelli non finali: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Tutto qui.

Esempio

Consideriamo questo automa:

L’automa che accetta il complemento del linguaggio sarebbe fatto così:

Fonti

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