2
$\begingroup$

This is a question involving regular expressions for regular languages.

I am currently stuck trying to prove that the operand ∅ is not necessary unless the language is the empty set. That is, a regular expression is either equivalent to ∅ or is a ∅-free regular language. (A language is ∅ free if it contains no occurences of ∅)

This seems to be an induction proof, but I'm not really sure how to prove this. It seems like you're possibly trying to show that if a set is ∅ free, then doing anything involving ∅ will either result in the language ∅ or a ∅ free language.

So if r is ∅ free, then (r+∅) = r, r∅=∅ etc

I'm not really sure if this is really complete. I'm not overly comfortable with regular languages yet, so any help is much appreciated.

|cite|improve this question
$\endgroup$
3
$\begingroup$

Preforming the proof by induction on the structure of the tree is good way to go about this. I like to think about how I would write a program to remove them because this directly leads to a constructive proof.

Say our regular expressions have the following form

$$ \begin{align} regex ::=& \,\, regex \,\, regex \\ |& \,\, regex^* \\ |& \,\, regex^+ \\ |& \,\, regex\,? \\ |& \,\, regex + regex \\ |& \,\, char \\ |& \,\, \varnothing \end{align} $$

The bases cases are the cases in which the regex is either a character or $\varnothing$

To give an inductive step say we have a regular expression of the form $regex + regex$. We can then recursively convert the two sub parts to regular expressions which either are the empty set or contain no empty set. So we have 4 cases

case 1: Both expressions contain no $\varnothing$ in which case we are done

case 2/3/4: One of the sides (possibly both) is $\varnothing$ so we remove that side. One needs to prove that this is valid but it isn't hard.

all the cases are going to precede as such with different proofs that the empty set can be eliminated.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ It seems we need more information on the precise expressions before we can answer the question. How would you avoid using $\{\lambda\}=\varnothing ^*$ with your grammar? $\endgroup$ – Hendrik Jan Nov 29 '15 at 11:54
  • $\begingroup$ I'm sorry, I don't understand the question. Would you mind rephrasing? I don't know what you mean by the equation you presented in particular. One thing that I have left out for sure is the semantics for the regular expressions. This is key in proving that things like $\varnothing^* \equiv \varnothing$ but this part is left as an exercise. $\endgroup$ – Jake Nov 29 '15 at 12:09
  • 4
    $\begingroup$ The problem is that $\varnothing^* \neq \varnothing$ but $\varnothing^* =\{\lambda\}$, so in a way, we can create somting out of nothing. Hence we should have a separate way to write a regular expression for $\{\lambda\}$, which is not present in your grammar. $\endgroup$ – Hendrik Jan Nov 29 '15 at 12:14
  • 1
    $\begingroup$ Ah! Yea it would appear so. I'm used to $\epsilon$ being used instead of lambda. There is certainly no way to handle that as I have presented it. I suppose adding a lambda would solve it but I think that is probably not what the OP wanted. Clarification is needed indeed. $\endgroup$ – Jake Nov 29 '15 at 12:27

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.