Resumen: Semana del 3 al 10 de abril

(1/8)

Conversión de AFN a AFD

• Como ya se ha visto, un AFD tiene varias ventajas sobre un AFN, incluyendo la no ambigüedad y la compactación
• Por eso, es recomendable saber cómo convertir un AFN en un AFD

(2/8)

Conversión de AFN a AFD: procedimiento

• Los pre-requisitos serían los siguientes:
  • Crear una tabla de transiciones para el AFN
  • Seleccionar los elementos que pueden ser alcanzados desde el estado inicial a través de ϵ (la llamada cerradura épsilon)
  • Agruparlos como el conjunto de estados A, a partir del cual arranca el algoritmo
• Ya que tenemos A, se prosigue usándolo como base:
  • Por cada símbolo del alfabeto (excluyendo ϵ), se determina a qué estados se puede llegar desde todos los elementos del conjunto de estados A con ese símbolo (incluyendo las transiciones épsilon)
  • Cada nuevo conjunto de elementos se convierte en un nuevo conjunto de estados (B, C, etc.)
  • Por cada nuevo conjunto, se repite el procedimiento en cada uno
  • El procedimiento se repite hasta que todos los estados finales estén en un conjunto

(3/8)

Conversión de AFN a AFD: un ejemplo

• Tomando el último ejemplo del resumen anterior:

(4/8)

Conversión de AFN a AFD: un ejemplo (2)

• Con esa tabla podemos crear una tabla de transiciones:

• Ya con esos datos podemos crear una AFD con los valores dados:

(5/8)

Minimización de AFD

• Incluso después de crear una AFD, pueden existir estados reduntantes que dirijan al mismo lugar
• Por ejemplo, en el caso anterior, se puede notar que A, C y E dirigen con a a B y con b a C
• Para evitar la redundancia se utiliza un método de minimización

(6/8)

Minimización de AFD: procedimiento

• Primero se toman todos los estados, y se dividen en grupos: los finales por un lado y los no finales por otro
  • Por cada grupo:
    • Por cada símbolo del alfabeto:
      • Si todos los estados dirigen al mismo estado, se termina
      • Sino, se separan los estados que dirigen a estados que no estén incluidos en el grupo

(7/8)

Minimización de AFD: ejemplo

• Siguiendo con el ejemplo anterior, podemos dividir inicialmente el AFD en dos grupos: (ABCD), no finales y (E), final
• Por cada grupo y símbolo del alfabeto, tenemos que:
  • Con a, (ABCD) corresponde a (BBBB) y con b a (CDCE)
    • Como con a, todas apuntan a B, siguen todas juntas
    • Pero como con b, D apunta a E, que no está en el grupo, D se separa a un nuevo grupo
  • (E) es un caso final porque no puede ser dividido más
  • Por tanto, tenemos nuevos grupos, (ABC), (D) y (E)
  • Como sabemos que (D) y (E) no pueden continuar, sigamos sólo con (ABC)
  • Con a, (ABC) corresponde a (BBB) y con b a (CDC)
    • Con b, B apunta a D, que está fuera del grupo
  • Así, tenemos los grupos (AC), (B), (D) y (E); revisemos (AC)
    • Con a, (AC) corresponde a (BB) y con b a (CC); estamos en un caso final

(8/8)

Minimización de AFD: ejemplo (2)

• Al final se eliminan los estados "sumidero" (que acabamos de buscar) y los estados a los que no se puede llegar desde el estado inicial (en este caso A)
• Así tenemos que (AC) son el mismo grupo, así que podemos unificarlos en un solo estado para que dejen de ser un "sumidero"
• E se conserva por ser el estado final