3
$\begingroup$

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

$\endgroup$
  • $\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$ – Navjot Waraich Aug 24 '18 at 10:52
  • $\begingroup$ This is a standard fact included in any textbook or lecture notes on the subject. $\endgroup$ – David Richerby Aug 24 '18 at 15:01
4
$\begingroup$

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.

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

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.
$\endgroup$

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.