Ejercicios para la evaluación continua

Tema 5: No regularitat. Autòmats amb pila i jerarquia de Chomsky

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ó.

Autómatas amb pila i jerarquía de Chomsky

Ejercicio 1 Muestra un ejemplo de lenguaje inambiguo que no sea DCFL.

Ejercicio 2 Muestra un ejemplo de DCFL que no sea regular.

Ejercicio 3 Muestra que los lenguajes inambiguos i los DCFL no son cerrados por morfismo directo.

Ejercicio 4 Muestra que los lenguajes inambiguos i los DCFL no son cerrados por intersección.

Ejercicio 5 Muestra que los DCFL no son cerrados por reverso.

Ejercicio 6 Muestra que los lenguajes inambiguos i los DCFL no son cerrados por concatenación.

Ejercicio 7 Muestra que los lenguajes inambiguos i los DCFL no son cerrados por estrella.

Ejercicio 8 Sigui A regular, B CFL, C DCFL i \sigma un morfisme. Quins dels següents llenguatges podem assegurar que són regulars, quins podem assegurar que són DCFL, i quins podem assegurar que són CFL?
Raoneu les respostes, i doneu contraexemples quan sigui necessari.

  1. \sigma^{-1}(B)\cap A.
  2. \overline{\sigma^{-1}(C)}.
  3. C^R.
  4. S(C) (recordeu la definició de shiftar un llenguatge donada en els problemes del primer tema).
  5. S(A).
  6. (\overline{A\cap C}\cup B).
  7. (\sigma(B)\cap B)C.
  8. (\overline{A}-\sigma(B)\cap\overline{C}).
  9. (\sigma^{-1}(\sigma(B))\cap B) C.
  10. \overline{(\overline{\sigma(A)}\cap C)}\sigma(B\cap A).
  11. \sigma(\sigma^{-1}(B)\cap A)\sigma^{-1}(C).

Ejercicio 9 Propón un algoritmo de coste razonable para saber, dado un DFA A i una CFG G, si se cumple {\mathcal L}(G)\subseteq {\mathcal L}(A).

Ejercicio 10 Propón un algoritmo de coste razonable para saber, dado un DFA A i una CFG G, si G genera infinitas palabras no aceptadas por A.

Ejercicio 11 Propón un algoritmo de coste razonable para saber, dado un DFA A i una CFG G, si G genera alguna palabra de tamaño par no aceptada por A.