⟸ Go Back ⟸
Exercise 12 (Homework 3).
(regular expressions)

Transformation of regular expressions

We say that two regular expressions p,q are equivalent (p\equiv q) if the languages represented by p and q (resp. L(p) and L(q)) are the same. To check whether two regular expressions p,q are equivalent one could always construct the associated DFAs and check whether they accept the same language. This is computationally expensive.1

This exercise is about checking the equivalence of two regular expressions using simple algebraic manipulations. Show that for all regular expressions p, q, and r:

  1. (p+q)^* \equiv p^*(qp^*)^*.
  2. p(qp)^* \equiv (pq)^*p.
  3. (p+q^*)^* \equiv (p+q)^*.
  4. If p\equiv q, then pr \equiv qr and rp \equiv rq.
  5. If L(q) \subseteq L(p), then p^*q^* \equiv q^*p^* \equiv p^*.
  6. p^* \equiv (\lambda + p)^* \equiv (\lambda + p)(p^*pp)^*.
  7. p^*pp + \lambda \equiv (p^*pp)^* \equiv (pp+ppp)^*.
  8. p^*(q+rp^*)^* \equiv (p+q^*r)^*q^*.
  9. (qq+qp+p)^*qpp^* \equiv p^*q(pp^*q+qp^*q)^*pp^*.
  10. (\lambda + b)a^*(b + bba^*)^* \equiv b^*(a + bb + bbb)^*b^*.

To prove some of the items (especially, the last three), it is useful to apply previous equivalences.

Footnotes

  1. Deciding whether two regular expressions are equivalent is PSPACE-complete, i.e., informally, it is the hardest among the decision problems solvable using a polynomial amount of memory, but no limitations on the running time.↩︎