⟸ pàgina anterior ⟸
Exercici 12 (Tasca 3).
(regular expressions)

Transformació d’expressions regulars

Diem que dues expressions regulars p,q són equivalents (p\equiv q) si els llenguatges associats a p i a q (resp. L(p) i L(q)) són iguals. Per comprovar si dues expressions regulars p,q són equivalents, sempre podríem construir els DFAs associats i comprovar si accepten el mateix llenguatge. Això és car computacionalment.1

Aquest exercici tracta sobre l’equivalència d’expressions regulars basada en manipulacions algebraiques senzilles. Demostreu que per a qualssevol expressions regulars p, q i r:

  1. (p+q)^* \equiv p^*(qp^*)^*.
  2. p(qp)^* \equiv (pq)^*p.
  3. (p+q^*)^* \equiv (p+q)^*.
  4. Si p\equiv q, llavors pr \equiv qr i rp \equiv rq.
  5. Si L(q) \subseteq L(p), llavors 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^*.

Per demostrar alguns apartats (especialment, els tres darrers), és útil aplicar equivalències prèvies.

Notes a peu de pàgina

  1. Decidir si dues expressions regulars són equivalents és PSPACE-complet, és a dir, informalment, és entre els problemes decisionals més difícils que requereixen una quantitat polinòmica de memòria, però sense limitacions sobre el temps de càlcul.↩︎