How to make a recursive definition for a given predicate?

Question

I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression:

• $r=\emptyset$
• $r=\varepsilon$
• $r=a:\forall\in\Sigma$
• $r=e+f$
• $r=ef$
• $r=e^*$

Now I have to write a recursive definition for $empty(r)$. And this is the thing where I have some problems with. I know that we need at least one basecase and at least one case where the definition calls itself with a reduced problem. I understand the predicate as the following: "If L is empty empty(r) is false, otherwise it's true". I started with the basecases:

$$empty(\emptyset)=true$$

$$empty(\varepsilon)=false$$

The first base case is pretty much self explained. My plan was to somehow reduce the regular expressions so much until they are only $\varepsilon$ and I thought that I could use the fact that every regular expression can be combined with $\varepsilon$ like this: $$r\Leftrightarrow\varepsilon r$$ But I still don't understand how I should build the definition for $empty(r)$. And maybe someone here can help me.

It would be nice as well if someone could give a hint on how I could proof the definition when I found one. I am grateful for every answer and comment!

Answer 1

Let $L, L_1, L_2$ be regular languages.

• if $L = L_1\cup L_2$, then $L$ is empty if and only if $L_1$ is empty AND $L_2$ is empty;
• if $L = L_1L_2$, then $L$ is empty if and only if $L_1$ is empty OR $L_2$ is empty;
• if $L = L_1^*$, then $L$ is not empty.

That should do it for induction.