Complement of a regular language

Let L be a regular language. We will prove that the complement of the language L is again a regular language.

What the complement is

By the complement of a language L we mean all the strings that are not in the language L. We write the complement as L^c. That is, for an alphabet Σ:

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

For example, for the language of strings containing at least one symbol 1, the complement would be the language of strings that contain no symbol 1 at all.

Construction

The construction is very simple. We have a regular language L and a deterministic complete automaton A = ⟨Q, Σ, δ, q₀, F⟩ that accepts it (every finite automaton can be converted to one). We construct the automaton A^c, which accepts L^c, by swapping the accepting and non-accepting states: A^c = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. That is all.

Example

Let this be our automaton:

The automaton accepting the complement of the language would look like this:

Sources

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