# Is DFA and Regular Expression equivalent?

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)?

• As you are new, you might not be able to upvote the answer but you can accept one by checking the tick mark. – Navjot Waraich Aug 24 '18 at 10:52
• This is a standard fact included in any textbook or lecture notes on the subject. – David Richerby Aug 24 '18 at 15:01

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.

• By the way, does the empty set symbol exist in regular expression used in may programming languages (like Perl, Java, and Python)? – Eric Stdlib Aug 25 '18 at 11:48
• 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. – reinierpost Aug 25 '18 at 14:46
• Incidentally, the definitions of regular expressions I've seen in textbooks did not have the empty set symbol, either. – reinierpost Aug 25 '18 at 14:47

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.