We defined our regular expression language on page 12, lecture 2. The language c

Question

We defined our regular expression language on page 12, lecture 2. The language contains the operators * and +. We can eliminate r* from our language without reducing its expressiveness since r* has the same semantics as (r^+|epsilon). Can we eliminate r^+ from our language without reducing its expressiveness by using a semantically equivalent regular expression that uses r*? If yes, give the semantically equivalent regular expression. Can we eliminate both, r* and r^+, from the language without reducing the expressiveness? If yes, give the semantically equivalent regular expressions for the eliminated operators.

Explanation / Answer

First Part : We can eliminate r+ from our language without reducing its expressiveness by using a semantically equivalent regular expression that uses r*.Below is the equivalent regular expression :

r+ = r.r*

Explanation : r+ is interpreted as one or more instances r and r* is interpreted as zero or more instances of r. Therefore, we can interpret r+ as an instance of r followed by zero or more instance of r(r*).

Second Part : As far as i know we cannot remove both r+ and r* from a Regular Expression. Instead we can express r+ in terms of r* and vice-versa.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.