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^*$.