Complements in regular expressions

Question

Come up with a regular expression for the following language $$ \{w \mid w \text{ doesn’t contain the substring } 110\} $$ The book provides a more complex answer, but I think that using the complement is easier. Do you think this works?:
$\Sigma^*-\Sigma^*110\Sigma^*$

Answer 1

Your expression of the language as the complement of the language $\Sigma^*110\Sigma^*$ is correct. However, it does not give a regular expression for the language. A regular expression can only use letters, union, product and star operator (and the complement is not allowed). The fact that the complement of a language $L$ given by a regular expression can also be expressed by a regular expression is a nontrivial result, due to Kleene. The standard three step algorithm to find a regular expression for the complement of $L$ is the following:

Step 1. Find a deterministic complete automaton $\mathcal{A}$ accepting $L$.

Step 2. Find a deterministic automaton $\mathcal{B}$ accepting the complement $L$. This is the easy step: it suffices to modify $\mathcal{A}$ by replacing its set of final states by its complement.

Step 3. Convert the automaton $\mathcal{B}$ into a regular expression.