Cap8

Un autómata finito determinista tiene a lo sumo una transición desde cada estado con cualquier entrada. Si se está usando una tabla de transición para representar la función de transición de un AFD, entonces cada entrada en la tabla de transiciones es un solo estado. Como consecuencia, es muy fácil determinar si un autómata finito determinista acepta o no una cadena de entrada, puesto que hay a lo sumo un camino desde el estado de inicio etiquetado con esa cadena. El siguiente algoritmo muestra como simular el comportamiento de un AFD con una cadena de entrada.

AFD PARA ANALIZADORES LÉXICOS.

Otro enfoque para la construcción de un analizador léxico a partir de una especificación de LEX es utilizar un AFD para realizar la concordancia de patrones. La única diferencia es asegurarse de encontrar las adecuadas concordancias con los patrones. Cuando se convierte un AFN en un AFD utilizando el algoritmo para la construcción de subconjuntos, puede haber varios estados de aceptación en un subconjunto dado de estados no deterministas. En tal caso, tiene prioridad el estado de aceptación correspondiente al patrón listado en primer lugar en la especificación de LEX. Como en la simulación del AFN, la única modificación que hay que realizar es continuar haciendo transiciones de estados hasta alcanzar un estado sin estado siguiente para el símbolo de entrada en curso. Para encontrar el lexema emparejado, se regresa a la última posición de entrada donde el AFD entró en un estado de aceptación.

ALGORITMO DE SIMULACIÓN DE UN AFD. ENTRADA: Una cadena de entrada x que termina con un carácter de fin de archivo. Eof. Un AFD D con un estado de inicio So y un conjunto F de estados de aceptación.

SALIDA:La respuesta si, si D acepta x, no en caso contrario.

MÉTODO: Aplíquese el algoritmo a la cadena de entrada x. La función mueve(s,c) da el estado al cual hay una transición desde el estado s en un carácter de entrada c. La función sigteca r devuelve el siguiente carácter de la cadena de entrada x.

Return "sí"

Else return "no"

REGRESAR
CONTINUAR

SACBEOB TE REGALA ESTOS SERVICIOS

INFORMACION PUBLICITARIA TUTORIALES SACBEOB LIGAS A OTROS TUTORIALES TU E-MAIL GRATIS CON SACBEOB CONOCE SACBEOB

CONOCE AL PERSONAL UVM BAJA PROGRAMAS PROGRAMAS COMUNIDAD ESTUDIANTIL LIGAS A PAGINAS PERSONALES SACBEOB|UVM|MEXICO

SACBEOB|UVM|EDO.MEXICO NOTICIAS DEPORTIVAS NOTICIAS CULTURALES EVENTOS-INFORMACION DE LA UVM MAESTRIAS

BOLSA DE TRABAJO

SOCIEDAD DE ALUMNOS DE SISTEMAS