Ejercicios para la evaluación continua

Tema 4: Expressions Regulars

Leyenda

= el ejercicio ha sido asignado a un/una estudiante/a y será resuelto en clase.
Para ver la asignación (y la fecha de entrega) consulta el racó.

Ejercicio 1 Trobeu expressions regulars que representin els següents llenguatges transformant un DFA en una expressió regular segons el mètode basat en el lema d’Arden.

  1. Mots sobre \{a,b\} amb un nombre parell de a’s.
  2. Mots sobre \{a,b\} amb o bé un nombre parell de a’s, o bé un nombre parell de b’s.
  3. Mots sobre \{a,b\} acabats en ababa.
  4. Mots sobre \{a,b\} que no contenen el submot aba.
  5. Mots sobre \{a,b,c\} tals que, entre cada dues a’s hi ha almenys una b.
  6. Mots sobre \{0,1\} amb almenys dos 0’s consecutius.

Ejercicio 2 Donada una expressió regular, com construirieu una altra expressió regular, de manera senzilla, que generi el llenguatge revers de la primera?

Ejercicio 3 Donada una expressió regular r i un morfisme \sigma, com construirieu una altra expressió regular, de manera senzilla, que generi \sigma({\mathcal L}(r))?

Ejercicio 4 Demostreu les equivalències següents entre expressions regulars:

  1. a^* (b + ca^*)^*= (a + b^*c)^*b^*
  2. (bb + ba + a)^*baa^* = a^* b (aa^*b + ba^*b)^*aa^*
  3. ( \Lambda + b) a^* (b + bba^*)^* = b^* (a + bb +bbb)^* b^*.

Ejercicio 5 Donades dues expressions regulars r_1 i r_2, com decidirieu:

  1. {\mathcal L}(r_1)={\mathcal L}(r_2).
  2. {\mathcal L}(r_1)\subseteq{\mathcal L}(r_2).
  3. {\mathcal L}(r_1)=\emptyset.
  4. |{\mathcal L}(r_1)|=\infty.
  5. |{\mathcal L}(r_1)\cap{\mathcal L}(r_2)|=0.
  6. |{\mathcal L}(r_1)\cap{\mathcal L}(r_2)|=\infty.

Ejercicio 6 (Lema d’Arden (bis)) Demostra que BA^* és solució de l’equació X=XA+B, que tota solució d’aquesta equació conté BA^*, i que en el cas de que A no contingui \lambda, aleshores BA^* n’és l’única solució.

Ejercicio 7 Aprofitant el resultat de l’exercici anterior (Lema d’Arden (bis)), obteniu una expressió regular pel complementari de les paraules que representen un múltiple de 3 (és a dir, \overline{\{w\in\{0,1\}^*\;|\; \mathtt{valor}_2(w)\in\dot{3}\}}). Per a això, escriu l’autòmat mínim per aquest llenguatge, crea una variable X_q per a cada estat q, i crea equacions (amb la incògnita a l’esquerra com en el Lema d’ Arden (bis)) amb la idea de que la solució de cada X_q sigui el llenguatge dels mots que ens porten des de l’ estat inicial a l’estat q.

Ejercicio 8 Utilitza el mètode de l’exercici anterior per obtenir expressions regulars dels llenguatges següents aplicant el Lema d’ Arden (bis). Compara-les amb expressions regulars que s’obtenen aplicant el Lema d’Arden tal i com s’explica en els vídeos.

  1. Mots sobre \{a,b\} amb un nombre parell de a’s.
  2. Mots sobre \{a,b\} amb o bé un nombre parell de a’s, o bé un nombre parell de b’s.
  3. Mots sobre \{a,b\} acabats en ababa.
  4. Mots sobre \{a,b\} que no contenen el submot aba.
  5. Mots sobre \{a,b,c\} tals que, entre cada dues a’s hi ha almenys una b.
  6. Mots sobre \{0,1\} amb almenys dos 0’s consecutius.