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 SinghCommented Aug 24, 2018 at 10:52
-
$\begingroup$ This is a standard fact included in any textbook or lecture notes on the subject. $\endgroup$– David RicherbyCommented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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.
answered Aug 25, 2018 at 18:19