# 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 '21 at 12:21