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$ $\endgroup$
2 
- $\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 Singh– Navjot Singh2018-08-24 10:52:16 +00:00Commented Aug 24, 2018 at 10:52
- $\begingroup$ This is a standard fact included in any textbook or lecture notes on the subject. $\endgroup$David Richerby– David Richerby2018-08-24 15:01:19 +00:00Commented Aug 24, 2018 at 15:01
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
4 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$Eric Stdlib– Eric Stdlib2018-08-25 11:48:55 +00:00Commented 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$reinierpost– reinierpost2018-08-25 14:46:07 +00:00Commented 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$reinierpost– reinierpost2018-08-25 14:47:44 +00:00Commented 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$Eric Stdlib– Eric Stdlib2020-04-06 22:28:21 +00:00Commented Apr 6, 2020 at 22:28
$\begingroup$ $\endgroup$
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:
- $r = \emptyset$. In this case $L[r] = \emptyset$.
- $r = \epsilon$. In this case $r$ is $\emptyset$-free.
- $r = \sigma$, where $\sigma \in \Sigma$. In this case $r$ is $\emptyset$-free.
- $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.
- $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.
- $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.
