What language can be created from a regular expression with nulls?

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

• 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? – fade2black Oct 4 '17 at 15:21
• @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. – David Richerby Oct 4 '17 at 15:22
• @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. – fade2black Oct 4 '17 at 15:27
• @fade2black No guessing is required. The question is completely clear (apart from the last paragraph) and I've written a comprehensive answer. – David Richerby Oct 4 '17 at 15:28
• @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. – fade2black Oct 4 '17 at 15:31

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.

• Would $\{∅\}$ be in $L(r_{1})$, where $r_{1} = cϵ+∅, Σ=\{c\}$? – Sean Francis N. Ballais Oct 4 '17 at 15:48
• @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)$.) – David Richerby Oct 4 '17 at 15:50
• @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$ – chi Oct 4 '17 at 15:51
• @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)? – Sean Francis N. Ballais Oct 4 '17 at 16:00
• @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. – David Richerby Oct 4 '17 at 16:09