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$.
1. If $L_1$, $L_2$ are regular lang then so is $L_1\bigcup L_2$.
2. If $L_1$, $L_2$ are regular lang then so is $L_1\circ L_2$.
3. If $L$ is a regular lang then so is $L^*$.
• I think you should add some sort of initialization i.e. $$(\forall x\in \Sigma)(\{x\}\mbox{ is regular})$$ – Duchamp Gérard H. E. Nov 17 '16 at 19:13

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)}$.

• I appreciate the answer but I am only allowed to use regular languages, regular expressions, languages, and their properties. So I can't use this explanation as well. – Liron Ilayev Nov 17 '16 at 12:28
• @LironIlayev: Doesn't "and their properties" in principle cover everything you might want to throw in? – Henning Makholm Nov 17 '16 at 12:53
• @HenningMakholm Only the three mentioned are allowed to use – Liron Ilayev Nov 17 '16 at 12:54
• @HenningMakholm Is this even solveable with the terms mentioned above? Maybe some sort of induction? – Liron Ilayev Nov 17 '16 at 12:59
• @LironIlayev: One of "the three mentioned" is "and their properties". The fact that regular languages can be recognized by automata is one of the properties of regular languages and is therefore, by your own definition, an allowed technique. – Henning Makholm Nov 17 '16 at 13:33

This is an interesting question. I interpret your requirements as giving a proof of the closure under complement dealing only with regular expressions. But there is no such proof.

Short answer. Such a proof would give a proof that in any monoid, the set of rational subsets is closed under complement. However this is not true, for instance in the monoid $a^* \times \{b,c\}^*$: see this page for a short proof.

Details.

Recall that a monoid is a set $M$ equipped with an associative operation (denoted multiplicatively) and an identity element $1$. Then $\mathcal{P}(M)$, the set of subsets of $M$, is equipped with an addition, the usual set union (that is $X + Y = X \cup Y$ by definition), and a product: $XY = \{xy \mid x \in X, y \in Y \}$. Finally, if $X$ is a subset of $M$, then $X^*$ is the submonoid of $M$ generated by $X$. Note that $X^* = \{1\} + X + X^2 + \cdots\$ The set of rational subsets of $M$ is the smallest subset of $\mathcal{P}(M)$ containing the singletons $\{m\}$ (for $m \in M$) and closed under the three operations sum, product and star. As you can see, in the case of a free monoid, you recover the usual notion of regular language.

By the way, the notion introduced by Gérard Duchamp in his answer also extends to any monoid: a subset $X$ of a monoid $M$ is recognizable if there exists a monoid morphism $\varphi$ from $M$ onto a finite monoid $F$ and a subset $P$ of $F$ such that $\varphi^{-1}(P) = X$.

Now, Kleene's theorem implies that in a free monoid, a subset is rational if and only if it is recognizable. However, this equivalence does not hold in any monoid: for instance in $\mathbb{Z}$, $\{0\}$ is rational but not recognizable. It is more difficult to find examples for which the rational sets are not closed under intersection (and hence under complement), but an example is given in the short answer.

• Thank you for clarification (+1) – Duchamp Gérard H. E. Nov 18 '16 at 20:16