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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.