Regular Language Supplement
Kapitoly: Closure of regular languages, Unification, Access, The Difference, Supplement, Concatenation, Conclusion
We have a regular language L. We prove that the complement of L is again a regular language.
What is a complement
By the language complement L we mean all words that are not in the language L. We denote the complement by L' I.e., for the alphabet $\Sigma$ it holds that:
$$ L' = \left\{w \in \Sigma^\ast,|, w \notin L\right\}. $$
For example, for a language of words containing at least one symbol 1, a complement would be a language that contains words that do not contain even one symbol 1.
Procedure
The procedure is very simple. We have the regular language L and the automaton $A=\left<Q, \Sigma, \delta, q_0, F\right>$, which connects it. We construct the automaton A', which accepts L' by swapping the terminal and non-terminal states: $A'=\left<Q, \Sigma, \delta, q_0, Q\setminus F\right>$. That's it.
Example
Let's have this automaton:
An automaton receiving a language complement would look like this:
