Diagramas de estado finito

Para representar gráficamente un aceptor de estado finito, también se utilizan losdiagramas de estado finito o diagramas de transición, como el que se muestra en la siguiente figura y que representa el aceptor para un número con al menos un dígito después del punto decimal.

Los nodos del diagrama de estado finito representan los estados del aceptor de estado finito. En el diagrama anterior, los nodos se han etiquetado con los números 1, 2 y 3. Los arcos, que van de un estado otro, indican lastransiciones de estado.

La flecha y la palabra «Inicio» indican cual de los estados es el estado inicial (en este caso el estado 1). El estado etiquetado con el 3 se denomina estado final.

Generalmente los estados finales se representan por medio de dos círculos concéntricos, pero en nuestro caso, para facilitar su construcción, hemos utilizado un circulo con línea más gruesa. Los símbolos sobre los arcos representan los caracteres que, al leerse, obligan al cambio de un estado a otro.

Un diagrama de transición es una representación gráfica donde se tiene un conjunto de estados, los cuales pueden ser:

– iniciales
– finales
– intermedios
los cuales pueden tener una o más salidas hacia otro estado. 

Los estados se relacionan entre sí con flechas con un nombre (el caracter o conjunto de caracteres que provoca la transición de un estado a otro). Un estado final se representa con:

que también recibe el nombre de estado de aceptación.

Para construir un diagrama de transición se debe tener presente:

A cada estado debe llegarse con el mismo conjunto de caracteres en todas las ocasiones en que haya un transición.

Para llegar a un estado de aceptación debe existir una transición sobre el caracter que rompe el patrón de la unidad de léxico.

Cuando se construye un analizador de léxico utilizando diagramas de transición para la especificación de los patrones, se realiza un único diagrama que, a partir del estado 0, tiene diversas transiciones a cada uno de los patrones de las unidades de léxico que deba reconocer. Cada patrón posee un caracter selector, que permite reconocer de manera única el patrón que deba aplicarse.

Por ejemplo, si queremos reconocer identificadores, comentarios apegados a las reglas del lenguaje C y el fin de archivo, podriamos contruir el siguiente diagrama:

Las descripciones informales de las unidades de léxico son:

– Identificador: Letra seguida de letra, dígitos o guione
– Comentario: Empieza con /* y termina con */. Entre estos pares puede haber cualquier símbolo
– EOF: cuando se encuentra el caracter eof (fin de archivo)
– Error: Cualquier símbolo que no cumpla con los patrones anteriores.

Los caracteres selectores para cada patrón son:

– Identificador: letra
– Comentario: /
– EOF: eof
– Error: cualquier símbolo diferente a los anteriores.

En el diagrama también aparecen otros estados derivados de patrones incompletos; estos estados se clasifican como Error.