Hoja 5 (23 de Marzo de 2010)

P1: Convierte el siguiente AFND–ε en un AFND (incluye todas las tablas, grafos, quintuplas, y el cálculo de la clausura transitiva necesario). El estado inicial es el estado 1.

AFND-E hoja 5

Hagamos memoria una quintupla se representa por esta formula Quintupla base donde:

  • Alfabetoes un alfabeto
  • conjunto de estadoses un conjunto finito no vació de estados
  • funcion de Transiciones una función de transición
  • conjunto de estados inicialeses el estado inicial
  • F es el conjunto de estados finales

Para el AFND–ε la quintupla estará formada por:

  • Alfabeto={a,b,ε}
  • conjunto de estados={1,2,3,4,5,6}
  • funcion de Transicionla tabla de transición
  • conjunto de estados iniciales={1}
  • F={2,4}

Creamos la tabla de transición para el AFND-ε

Elemento a b

epsilon

1

{6} {emptyset} {2}

2

{3} {2} {emptyset}

3

{4} {emptyset} {6}

4

{emptyset} {3,5} {emptyset}

5

{3} {emptyset} {emptyset}

6

{emptyset} {5} {4}

ahora calculamos las clausuras para cada elemento

Por clausura de un elemento entendemos el conjunto de estados a los que podemos acceder sin consumir ninguna símbolo , el propio elemento al que le calculamos su clausura  pertenecerá a la misma.

para que quede mas claro, para el elemento 3 su clausuara estara compuesta por 3, 6 “(3,ε)=6” y 4 “(6,ε)=4”

Elemento a b epsilon clausura
1 {6} {emptyset} {2} {1,2} = Cl(1)
2 {3} {2} {emptyset} {2} = Cl(2)
3 {4} {emptyset} {6} {3,6,4} = Cl(3)
4 {emptyset} {3,5} {emptyset} {4} = Cl(4)
5 {3} {emptyset} {emptyset} {5} = Cl(5)
6 {emptyset} {5} {4} {6,4} = Cl(6)

Ahora creamos una nueva tabla eliminando la columna de ε  y substituyendo  los estados de destino para cada elemento del alfabeto por la unión de los estados de destino de la clausura. Por ejemplo para el elemento 1 la clausura es {1,2} y para la transición con a debemos incluir 6 para el estado 1 y 3 para el estado 2. por lo tanto nos queda el conjunto {6,3}.

delta a b
Cl(1)

{6,3}

{2}

Cl(2)

{3}

{2}

Cl(3)

{4}

{3,5}
Cl(4) {emptyset} {3,5}
Cl(5)

{3}

{emptyset}
Cl(6) {emptyset} {3,5}

una vez realizada esta tabla creamos la ultima tabla substituyendo cada estado destino de la  tabla anterior por la clausura del mismo

delta a b
Cl(1)

{3,4,6}

{2}

Cl(2)

{3,4,6}

{2}

Cl(3)

{4}

{3,4,5,6}

Cl(4)

{emptyset}

{3,4,5,6}

Cl(5)

{3,4,6}

{emptyset}

Cl(6)

{emptyset}

{3,4,5,6}

Ahora ajustamos los estados para añadir los iniciales y los finales. Si en la clausura de un  elemento existe un estado inicial este es inicial (marcados verde en la segunda tabla) y si existe un estado final este es final (marcados de rojo en la segunda tabla) con esto ya tenemos el AFND sin transiciones epsilon

delta a b
*->Cl(1)

{3,4,6}

{2}

*Cl(2)

{3,4,6}

{2}

*Cl(3)

{4}

{3,4,5,6}

*Cl(4)

{emptyset}

{3,4,5,6}

Cl(5)

{3,4,6}

{emptyset}

*Cl(6)

{emptyset}

{3,4,5,6}

Para el AFND la quintupla estará formada por:

  • Alfabeto={a,b}
  • conjunto de estados={1,2,3,4,5,6}
  • funcion de Transicionla tabla de transición
  • conjunto de estados iniciales={1}
  • F={1,2,3,4,6}

Modelamos el nuevo autómata en JFlap

AFND Cargamos el otro en JFlap

dos autómatasEn la ventana de cualquier autómata seleccionamos el menú  test y la opción “compare equivalence” y seleccionamos el otro automata

comparar dos autómatas

pinchamos en aceptar y son equivalentes

son equivalenteslo que significa que aceptan el mismo lenguaje

7 Replies to “Hoja 5 (23 de Marzo de 2010)”

  1. Bueno, aquí está el pesao de turno para darte una nueva solución jajaj. Utilizo un método diferente para obtener dicho autómata equivalente (las tablas son siempre así, solo cambia la forma de transformarla en autómata).

    Cogiendo la tabla final, empiezo creando el estado inicial 1, que también será final en este caso. Después, con “a”, iría a un nuevo estado que denomino “3,4,6”, y con “b” a un estado “2”. Podemos decir que el estado “3,4,6” es un conjunto de los estados 3, 4 y 6 del autómata original. Para saber a dónde vamos con “a” desde dicho estado, seguimos el siguiente procedimiento:

    – Desde el estado 3 con “a” iríamos al estado 4
    – Desde el estado 4 con “a” no iríamos a ningún estado.
    – Desde el estado 6 con “a” no iríamos a ningún estado.

    Así pues, desde el estado “3,4,6” iríamos, con “a”, al conjunto de los estados a donde iríamos individualmente con 3, 4 y 6, que en este caso sería “4”.

    Seguimos el mismo paso para saber a dónde vamos con “b” desde el estado “3,4,6”:

    – Desde el estado 3 con “b” vamos al estado “3,4,5,6”.
    – Desde el estado 4 con “b” vamos al estado “3,4,5,6”.
    – Desde el estado 6 con “b” vamos al estado “3,4,5,6”.

    Y por tanto, ya sabemos que desde el estado “3,4,6” iríamos, con “b”, a un nuevo estado que sería “3,4,5,6”.

    Se debe realizar dicho procedimiento con cada nuevo “estado de estados” que obtengamos, hasta que hayamos realizado todos los caminos posibles que nos describe la tabla.

    Siguiendo dichos pasos se puede obtener un autómata equivalente con tan solo 5 estados (todos finales), los cuales renombramos con letras o números simples para simplificar la nomenclatura (es un poco lioso si tenemos estados con nombres “3,4,5,6” o similares).

    Sé que es complicado de entender de forma escrita sin un ejemplo gráfico (además de que no me explico demasiado bien jajaj).

    Un saludo!!

  2. Muchas gracias por esta página, no había encontrado una tan buena. Me va a ayudar muchísimo en mi asignatura de Computabilidad y Algoritmia.

      1. Hola tengo una duda en el ejercicio 3 de la práctica 4. Hay que diseñar un AFD usando el método del complemento. Los estados de aceptación del AFD original no serían el q1, q3, q4 y q2?
        Si en el AFD complemento lo que se hace es cambiar los estados de aceptación del AFD original por no aceptación y viceversa, por qué en éste AFD tienes como nuevos estados de aceptación el q0 y el q2? En este nuevo AFD el único estado d aceptación no sería el q0? Saludos y gracias.

        1. haces un autómata que solo acepte solo palabras que comiencen por abab.
          Después intercambias estados finales por no finales y viceversa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.