The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?

If Regular Expression cannot do that, does it mean that DFA and Regular Expression are not equivalent (in at least some cases)?

  • $\begingroup$ As you are new, you might not be able to upvote the answer but you can accept one by checking the tick mark. $\endgroup$ Aug 24, 2018 at 10:52
  • $\begingroup$ This is a standard fact included in any textbook or lecture notes on the subject. $\endgroup$ Aug 24, 2018 at 15:01

2 Answers 2


According to Wikipedia:

Given a finite alphabet $\Sigma$, the following constants are defined as regular expressions:

  • (empty set) $\emptyset$ denoting the set $\emptyset$.

  • ...

... a string that contains only an empty-set symbol is a regular expression, which represents the empty language.

  • $\begingroup$ By the way, does the empty set symbol exist in regular expression used in may programming languages (like Perl, Java, and Python)? $\endgroup$ Aug 25, 2018 at 11:48
  • $\begingroup$ No, they do not have the empty set symbol, nor the empty string symbol (those are different things). They do have the empty expression (consisting of 0 symbols), which matches the empty string. $\endgroup$ Aug 25, 2018 at 14:46
  • $\begingroup$ Incidentally, the definitions of regular expressions I've seen in textbooks did not have the empty set symbol, either. $\endgroup$ Aug 25, 2018 at 14:47
  • $\begingroup$ I just realized you can match empty string using re.fullmatch('a{0}', '') in Python, which is kind of an alternative to empty set symbol. $\endgroup$ Apr 6, 2020 at 22:28

Complementing xskxzr's answer, let me mention that if $L$ is a non-empty regular language, then $L$ has a regular expression not involving $\emptyset$; so we only need $\emptyset$ to accommodate the empty language.

This claim can be proved in many ways. One option is by induction on regular expressions. Let us prove the following claim by induction: if $r$ is a regular expression, then either $L[r] = \emptyset$, or $L[r] = L[s]$ for some $\emptyset$-free regular expression $s$.

We need to consider six cases:

  1. $r = \emptyset$. In this case $L[r] = \emptyset$.
  2. $r = \epsilon$. In this case $r$ is $\emptyset$-free.
  3. $r = \sigma$, where $\sigma \in \Sigma$. In this case $r$ is $\emptyset$-free.
  4. $r = s^*$. If $L[s] = \emptyset$ then $L[r] = \{ \epsilon \} = L[\epsilon]$. Otherwise, we can assume that $s$ is $\emptyset$-free, and then $r$ is also $\emptyset$-free.
  5. $r = st$. If $L[s] = \emptyset$ or $L[t] = \emptyset$ then $L[r] = \emptyset$. Otherwise, we can assume that $s,t$ are $\emptyset$-free, and then $r$ is also $\emptyset$-free.
  6. $r = s + t$. If $L[s] = L[t] = \emptyset$ then $L[r] = \emptyset$. If $L[s] = \emptyset$ and $L[t] \neq \emptyset$, then $L[r] = L[t]$, and we can assume that $t$ is $\emptyset$-free. The case $L[t] = \emptyset$ and $L[s] \neq \emptyset$ is symmetric. Finally, if $L[s],L[t] \neq \emptyset$ then we can assume that $s,t$ are $\emptyset$-free, and then $r$ is also $\emptyset$-free.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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