sábado, 12 de julio de 2008

Algoritmo de un AFD genérico


Este algoritmo fue desarrollado para un curso de tercer ciclo: Teoría de la Computación.
Consiste en, hacer un algoritmo que reciba como entradas un autómata, y una palabra;
y que devuelva como resultado, si la palabra es reconocida o no por el autómata.
Es decir:

Algoritmo:
Autómata finito determinista general para reconocer palabras

Entrada:
- AFD como 5-tupla: donde:
  • es el Conjunto de Estados/Variables
  • es el Alfabeto
  • es la función de transición
  • es el estado inicial
  • es el Conjunto de estados finales
- palabra a evaluar.

Salida:
- Valor booleano que determina si la palabra evaluada pertenece al AFD.

Proceso:
1. Hacer la lectura del AFD
  • Leer : estado inicial // representado por un número
  • Leer : Conjunto de estados // representado por un arreglo de números
  • Leer : vocabulario // representado por un arreglo de caracteres
    que pertenecen a
  • Dados los tamaños de y de ,
    crear una matriz de tamaño
    para representar/almacenar las transiciones
    rellenando con en donde no hay transición
  • Leer : Conjunto de estados finales
2. Leer palabra a evaluar.

3. Analizar la palabra:
Tenemos el estado actual/temporal (el cual evalúa según momento)
Tenemos el valor booleano
Para cada caracter , mientras no termine la palabra:

si y

sino
error: palabra no reconocida


Comentarios adicionales:
1. En aquella época no sabía manejar GUIs, por eso la precariedad del programa.
Ahora se vería más bonito e interesante con un creador gráfico de estados y transiciones:


2. Me quedaba la duda de: siempre S0 será el estado inicial? (Y así, omitir el paso 1.1. del algoritmo)
3. Imágenes, cortesía de Wikipedia

3 comentarios:

  1. buenas, te agradeceria si me pasaras unos link acerca de GUIs para crear gráficos
    de estados y transiciones.

    ResponderBorrar