AFN A AFD

GRUPO#3 PRESENTA

CONVERTIR UN AFN A UN AFD

EQUIPO

SARAI

JOSE

CESAR

aLICIA

EDINSON

Introducción

Un reconocedor de un lenguaje es un programa que toma como entrada una cadena “x y”, responde "si" si x es una frase del programa, y "no", si no lo es. Se compila una expresión regular en un reconocedor construyendo un diagrama de transiciones generalizado llamado autómata finito. Un autómata finito puede ser determinista o no determinista, donde "no determinista" significa que en un estado se puede dar el caso de tener mas de una transición para el mismo símbolo de entrada.

DEFINICIÓN de problema

Se pidio la compilación de un programa que al ser ejecutado nos permitiers convertir un automata afn a afd.

dIAGRAMA DE TRANSICIONES

TABLA DE TRANSICIONES

codigo fuente

codigo fuente

codigo fuente

codigo fuente

codigo fuente

Objetivos

Determinar la conversión de un AFN A UN AFD

Poder compilar el programa visto en clase para conocer más de su funcionamiento

Conclusiones

-Este algoritmo conocido como el de construcción de subconjuntos convierte un AFN en un AFD haciendo uso de tres operaciones sobre los estados de un AFN y una pila. Lo importante del algoritmo es que se procesa el conjunto de estados del AFN denominado “T”, usando operaciones de una estructura llamada pila.

Recomendaciones

-Si se desea correr el programa con un AFN diferente se debe inicializar la matriz de estados dentro del programa. Esto es conveniente cuando el AFN a convertir tiene un número de estados mayor de 5; pues de lo contrario se tendrían que ingresar estos por teclado lo cual aumenta la probabilidad que se introduzcan datos incorrectos. Otra alternativa cuando la entrada es muy grande, es guardar los datos de entrada en un archivo para luego ser tomados por el programa.

GRACIAS !