Complement of regular language is regular The Question
Let $L$ be a regular language. Prove the $\overline{L}$ is a regular language without using automata.
Explanation
I have an assignment to solve without using automata at all. To solve one of the questions I want to use the following: "If $L_1$, $L_2$ are regular languages, then $L_1\bigcap L_2$ is a regular language". The properties allowed to use are listed in "Allowed to use only".
So I thought of using De Morgan's law: $L_1\bigcap L_2$ = $\overline{\overline {L_1}\bigcup \overline{L_2}}$
But complement is not one of the properties allowed to use. If you can show the intersection is a regular without complement and without automata that would be good as well.
Allowed to use only


*

*Alphabet $\Sigma$ set of symbols, final. 

*Word $w$ finite
concatenation of symbols from $\Sigma$ and final.

*Sigma Kleene star $\Sigma ^*$ all words with symbols from $\Sigma$ including $\varepsilon$ the empty string.

*Language $L$ subset of $\Sigma ^*$.

*Let $L$ $M$ be languages under $\Sigma$. Then $L\bigcup M$, $L\bigcap M$, $L\circ M$, $\overline{L}$, $\overline{M}$, are also languages under $\Sigma$.

*Language $L$ is regular, if there exists a regex r, that is a string under $\Sigma \bigcup $ {$ ∅, \circ, *, \bigcup $}, which defines $L$.


*

*If $L_1$, $L_2$ are regular lang then so is $L_1\bigcup L_2$.

*If $L_1$, $L_2$ are regular lang then so is $L_1\circ L_2$.

*If $L$ is a regular lang then so is $L^*$.



There is also an algebraic characterization of regular languages. 
A language $L\subset \Sigma^*$ is regular iff it exists an homomorphism (of monoids) $\phi : \Sigma^*\rightarrow M$ with $M$ a finite monoid and 
$$
L=\phi^{-1}(S)
$$ 
where $S\subset M$. You end using the formula $\phi^{-1}(\bar{S})=\overline{\phi^{-1}(S)}$.
