# How to show closure of regular languages without DFA,NFA,reg expressions

Given a $$\Sigma$$ I define a regular language as one of the folllows:

• $$\emptyset$$
• $$\left\{ \sigma \right\}$$ for any $$\sigma \in \Sigma$$
• $$L_1 \cup L_2$$ for regular $$L_1, L_2$$
• $$L_1 \cdot L_2$$ for regular $$L_1,L_2$$
• $$L^*$$ for regular $$L$$

Now, I would like to show that for a given regular language $$L$$, its complement $$\overline{L}$$ is regular as well. I want to do so based only on this definition (i.e. without proving its equivalent to DFA, NFA or reg expression).

However, I'm having a bit of trouble here, not sure how to do so. Maybe I want to express the complement of $$L$$ as a sort of unions/contactinations? Not really sure how to go for it. Any ideas?

Your definition is the same as the usual definition with regular expressions. While regular expressions also admit the empty word $$\epsilon$$, it is expressible as $$\emptyset^*$$.

There is no simple rule for complementing regular expressions, and it is known that such complementation can result in an exponential blow-up (for example, the language of all words not containing all alphabet symbols has a regular expression of size $$O(|\Sigma|^2)$$, but its complement requires a regular expression of length exponential in $$|\Sigma|$$).

• So there's no way of proving $\overline{L}$ is regular without a DFA/NFA? Nov 2, 2021 at 12:21
• None that I’m aware of. Nov 2, 2021 at 12:23

Complement means relative complement $$Σ^* - L$$. You already have closure under set subtraction and, in fact, also intersection and even interleave. So, the real question is how to do set-subtraction.

You can evaluate it algebraically, but you get a system that amounts to the description of a deterministic automaton. I will only illustrate it with a couple of examples, one of which will involve the relative complement with respect to $$Σ^*$$, where $$Σ = \{a,b\}$$.

Example 1: $$a b^* a - (ab)^*a$$:
Set $$A = a b^* a - (ab)^*a$$. Using the identity $$x^*y = y + x x^* y$$, we write $$A = a b^* a - (a + a b (a b)^* a) = a\left(b^* a - 1 - b (a b)^* a\right) = a B,$$ where $$B = b^* a - 1 - b (a b)^* a$$ and $$1$$ denotes the empty word.

The set-theoretic subtraction of $$1$$ is trivial since $$b^* a$$ does not contain the empty word. Therefore, we can write $$B = b^*a - b (a b)^* a$$. Thus, continuing on, we have $$B = a + b b^* a - b (a b)^* a = a + b\left(b^* a - (a b)^* a\right) = a C + b D,$$ where, $$C = 1$$ and $$D = b^* a - (a b)^* a$$.

For $$D$$, we have $$D = a + b b^* a - a - a b (a b)^* a = a\left(1 - 1 - b (a b)^* a\right) + b b^* a = b b^* a,$$ since the set-theoretic identity holds $$x - x - y = 0 - y = 0$$.

The resulting system $$A ≥ a B, B ≥ a C + b D, C ≥ 1, D ≥ b b^* a,$$ has to be written as a system of inequalities to avoid infinite regresses that occur if repeats of terms appear on the right-hand side (e.g. an equation like $$D = ⋯ + D + ⋯$$); and it is the least solution we seek out.

Solving for $$(C,D)$$ immediately yield the results $$(C,D) = \left(1, b b^* a\right)$$. Substituting into the other two inequalities yields $$A ≥ a B, B ≥ a + b b b^* a = \left(1 + b b b^*\right) a,$$ whose least solution is $$(A,B) = \left(a \left(1 + b b b^*\right) a, \left(1 + b b b^*\right) a\right).$$

The corresponding automaton has states $$A$$, $$B$$, $$C$$, $$D$$, plus whatever other states result from reducing the expression for $$D$$ to a system of inequalities. The start state is $$A$$, and $$C$$ is a final state, plus whatever other final state might come from the subsystem headed by $$D$$. (There are none. The subsystem headed by $$D$$ leads back to $$C$$ as its sole final state.) The expression of interest is that for $$A$$, and we can thus write $$ab^*a - (ab)^*a = a\left(1 + b b b^*\right)a.$$

Example 2: $$(a + b)^* - (a + b)^* b b (a + b)^*$$
Setting this expression to $$A$$, you can write $$A = 1 + a A + b \left(A - b (a + b)^*\right) = 1 + a A + b B,$$ where $$B = A - b (a + b)^*$$. In-line substituting this expression for $$A$$ into $$B$$ yields $$B = 1 + a A + b \left(B - (a + b)^*\right) = 1 + a A.$$ The last equality follows from the identity $$f(a,b) - (a + b)^* = 0$$, for any regular expression $$f(a,b)$$ in $$a$$ and $$b$$, since the set corresponding to $$(a + b)^*$$ is maximal. Thus, the corresponding system is $$A ≥ 1 + a A + b B, B ≥ 1 + a A,$$ which, upon in-line substitution of the expression for $$B$$ into $$A$$, yields $$A ≥ 1 + a A + b + b a A = 1 + b + (a + b a) A,$$ whose least solution is $$A = (a + b a)^* (1 + b)$$. Thus, $$(a + b)^* - (a + b)^* b b (a + b)^* = (a + b a)^* (1 + b).$$