Complement of regular language is regular

Question

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

Answer 1

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

Answer 2

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.

Answer 3

You simply take your definition of a regular language and prove the claim step by step for each type of regular expression. An expression $E$ is regular, if and only if it generates a language (a set of strings) $\mathcal L(E)$ through the use of concatenation, union and Kleene closure only. In other words:

1. $\mathcal L(\epsilon) = \{\epsilon\}$ is a regular language and $\epsilon$ the corresponding regular expression

2. $\mathcal L(\varnothing) = \emptyset$ is a regular language and the symbol $\varnothing$ the corresponding regular expression.

3. For every $\alpha\in\Sigma$, $\mathcal L(\alpha) = \{\alpha\}$ is a regular language and $\alpha$ the corresponding regular expression.

4. For any two regular expressions $R$ and $S$, $\mathcal L(R + S) = \mathcal L(S) \cup \mathcal L(S)$ is a regular language and $R + S$ the corresponding regular expression.

5. For any two regular expressions $R$ and $S$, $\mathcal L(R\circ S) = \mathcal L(S) \circ \mathcal L(S)$ is a regular language and $R \circ S$ the corresponding regular expression.

6. The language $\mathcal L(R^\ast) = \mathcal L(R)^\ast$ is regular and $R^\ast$ the corresponding regular expression.

Now you just need to think what the complement $\overline{\mathcal L(\cdot)}$ of each language $\mathcal L(\cdot)$ listed above is, and find regular expressions that generate them through the function $\mathcal L$. You will need the other properties you listed. Based on the hint you were given, the most significant rule is probably $\overline{\mathcal L(\cdot)} \cap \mathcal L(\cdot) = \emptyset$...