search

PUC-IIC2223 / syllabus2019

Repositorio oficial para el curso "Teoría de Autómatas y Lenguajes Formales" del año 2019
3 stars 0 forks source link

[T3 | P1] ¿Posible contraejemplo? ¿Determinización alternativa? ¿Minimización? #26

Open jmwielandt opened 4 years ago

jmwielandt commented 4 years ago

Hola!

Llevo mucho dándole vueltas al problema y no consigo llegar desde la determinización vista en clases a la cantidad de estados pedida.

Tomemos u = "LECHUGA" y v = "ZAPALLO". |u| = 7 y |v| = 7.

El NFA tendría 15 estados, hasta aquí todo bien.

Ahora, si hacemos la determinización vista en clases, algunos de los estados alcanzables son:

  1. (0)
  2. (0, (LECHUGA, 1))
  3. (0, (LECHUGA, 2))
  4. (0, (LECHUGA, 3))
  5. (0, (LECHUGA, 4))
  6. (0, (LECHUGA, 5))
  7. (0, (LECHUGA, 6))
  8. (0, (LECHUGA, 7))
  9. (0, (ZAPALLO, 1))
  10. (0, (ZAPALLO, 2))
  11. (0, (ZAPALLO, 3))
  12. (0, (ZAPALLO, 4))
  13. (0, (ZAPALLO, 5))
  14. (0, (ZAPALLO, 6))
  15. (0, (ZAPALLO, 7))
  16. (0, (ZAPALLO, 5), (LECHUGA, 1))

El estado 16 es alcanzable desde (0, (ZAPALLO, 4)) leyendo una 'L'. Y solo con eso, tengo 16 estados alcanzables, rompiendo que la cantidad de estados sea menor que |u| + |v| + 1.

Tengo un DFA que sí cumple con la propiedad y se puede construir a partir el NFA, sin embargo, de la respuesta de la issue #22 tengo que usar la determinización vista en clases y no una alternativa ni tampoco minimizarlo.

Quería saber en mi desesperación si hay algo que no estoy viendo del enunciado o de la materia :sob: Gracias u.u

PD: perdón por la publicación incompleta, es que CTRL + Enter es como un "enviar" y haciendo el copy paste para los estados, fallé en el tempo y me quedó Enter + CTRL + V :(

nicovsj commented 4 years ago

Hola José,

El problema con tu contraejemplo es que algunos de los estados que mencionas no son alcanzables desde (0). Por ejemplo, (0, (ZAPALLO, 5)). Te dejo que descubras el resto.

Saludos!