2
$\begingroup$

The usual regular expressions I have seen are those with non-null inputs (e.g. $a$, $b$). A few days ago, I saw, for the first time, a regular expression that has a null ($∅$) in it.

$$ r_{1}= (cε + d∅)^{*}, Σ = \{c,d\} $$

This confused me since I do not know how a language would be created from $r_{1}$.

What would a language created from a regular expression be like if that regular expression has a null (like $r_{1}$ above)?

Additionally, what would a language be like if the regular expression from which the language is created from contains $ε$ (for example, like $r_{2}=(aε)(bε)ε, Σ = \{a, b\}$, and again, like $r_{1}$ above)?

$\endgroup$
  • $\begingroup$ The formal definition of a regular expression requires a finite alphabet over which it is defined. What is the alphabet? Also, the empty string is usually denoted by $\epsilon$ or $\lambda$, not by $\emptyset$. It is not clear what $c$ and $d$ mean. Could you edit your post? $\endgroup$ – fade2black Oct 4 '17 at 15:21
  • $\begingroup$ @fade2black $\emptyset$ isn't being used to denote the empty string. $c$ and $d$ are, presumably, characters in the alphabet but it wouldn't make much difference if they were regular expressions, too. $\endgroup$ – David Richerby Oct 4 '17 at 15:22
  • $\begingroup$ @DavidRicherby I say the same thing, $\emptyset$ does not denote the empty string. $r_{1}= (cε + d∅)^* $ is not a regular expression, is it? We don't have to guess what the asker asks, the question should be clear and unambiguous. $\endgroup$ – fade2black Oct 4 '17 at 15:27
  • $\begingroup$ @fade2black No guessing is required. The question is completely clear (apart from the last paragraph) and I've written a comprehensive answer. $\endgroup$ – David Richerby Oct 4 '17 at 15:28
  • $\begingroup$ @DavidRicherby It should be written either in the set theoretic terms, in which case the $\emptyset$ is acceptable, or it should be written in terms of regular expressions. But by no means mixing, no matter the question is clear or not. $\endgroup$ – fade2black Oct 4 '17 at 15:31
4
$\begingroup$

The regular expression $\emptyset$ matches nothing at all: not the empty string, not any non-empty string.

Any concatenation with $\emptyset$ also matches nothing: a string would only match $d\emptyset$ if it could be divided into some part that matches $d$ and some part that matches $\emptyset$, but no such part exists. So $d\emptyset$ is the same thing as $\emptyset$: it matches nothing at all.

An alternation ("or") of something with $\emptyset$ has no effect: $c\epsilon+\emptyset$ means "anything that matches $c\epsilon$ or matches $\emptyset$" and that's just "anything that matches $c\epsilon$."

So $c\epsilon+d\emptyset$ is the same thing as $c\epsilon$ which, in turn, is the same thing as $c$. The regular expression you quote is equivalent to the simple $c^*$.


Conceptually, $\emptyset$ plays a similar role to zero in addition and multiplication. Adding zero to anything doesn't change it, just as alternation of a regular expression with $\emptyset$ doesn't change it. Multiplying anything by zero makes it equal to zero, just as concatenation of any regular expression with $\emptyset$ turns it into $\emptyset$.

$\emptyset$ might seem rather pointless as a regular expression. It's needed because, without it, the empty language (the one with no strings at all in it, i.e., the set $\emptyset$) wouldn't be regular. To see this, it's not hard to prove by induction that every regular expression that doesn't contain the character $\emptyset$ must match at least one string. However, we want the empty language to be regular, because it's accepted by an automaton – in fact, by any automaton with no accepting states.

$\endgroup$
  • $\begingroup$ Would $\{∅\}$ be in $L(r_{1})$, where $r_{1} = cϵ+∅, Σ=\{c\}$? $\endgroup$ – Sean Francis N. Ballais Oct 4 '17 at 15:48
  • $\begingroup$ @SeanFrancisN.Ballais That's a category error. Languages are sets of strings, and $\emptyset$ isn't a string. (So, no it's not in $L(c\epsilon+\emptyset)$, for the same reason that an elephant isn't in $L(c\epsilon+\emptyset)$.) $\endgroup$ – David Richerby Oct 4 '17 at 15:50
  • 1
    $\begingroup$ @SeanFrancisN.Ballais That question makes no sense: $L(r_1)$ is a set of words, so a set-of-sets which is not a word can not belong to that language. Anyway, as explained above $c\epsilon+\emptyset$ is equivalent to $c\epsilon$ $\endgroup$ – chi Oct 4 '17 at 15:51
  • $\begingroup$ @DavidRicherby I see. I get it more now. Would there be cases where $∅$ is necessary in regular expressions (aside from making sure the empty language is regular)? $\endgroup$ – Sean Francis N. Ballais Oct 4 '17 at 16:00
  • 2
    $\begingroup$ @SeanFrancisN.Ballais No, it's just for making the empty language regular. Any other regular expression that mentions $\emptyset$ is equivalent to one without it: you can use the rules $R\emptyset\equiv\emptyset$, $R+\emptyset\equiv R$ and $\emptyset^*\equiv\epsilon$ to remove $\emptyset$ from any regular expression that includes it. $\endgroup$ – David Richerby Oct 4 '17 at 16:09

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.