COMO DEFINIR TOTALMENTE UN AUTÓMATA FINITO DETERMINISTA
Cojamos el siguiente autómata, el cual, para el alfabeto
S = { a, b, c } reconoce la cadena c, la cadena a, las cadenas que empiezan por a y acaban en a o en b y las que empiezan por a, seguidas de una serie de a o de b y acaban en c. Su diagrama será:
1.- Diagrama de transiciones determinista
Visto el diagrama, podemos deducir que no está totalmente definido por los siguientes motivos:
- Si una cadena empieza por una b, no hay transición posible al estado 2 ó 3 desde el estado inicial.
- Si después de una c la cadena continua, caso en que la cadena debe ser rechazada, no tenemos ninguna transición que salga desde el estado 3 a algún estado de error.
Como podemos ver también, no salen desde un mismo estado más de un arco con la misma etiqueta, y por lo tanto podemos aplicar el siguiente método de conversión a un diagrama totalmente definido, para ello:
- Se añade un estado adicional que representará la función de
captación global (error)
- Situados en este nuevo estado, se dibuja un arco, el cual empieza y termina en
él mismo, por cada uno de los símbolos del alfabeto, etiquetado con dicho
símbolo.
- En cada estado se añade un arco por cada símbolo del alfabeto para el cual
no hay arco, con el cual se etiqueta, que se traza desde el estado correspondiente al nuevo
de captación.
Una vez terminamos, vemos que se cumple la definición de diagrama de transiciones determinista.
Para hacer la tabla de transiciones determinista, necesitamos tener definido totalmente el autómata. Para nuestro ejemplo, nos quedará la siguiente tabla:
| a | b | c | FDC | |
|---|---|---|---|---|
| Estado 1 | 3 | 4 | 2 | error |
| Estado 2 | 4 | 4 | 4 | aceptar |
| Estado 3 | 3 | 3 | 2 | aceptar |
| Estado 4 | 4 | 4 | 4 | error |
Tener en cuenta que en esta tabla se ha cambiado el nombre del estado de captación global ("error") por "estado 4".
© 1999 Roberto de la Fuente López. Todos los derechos reservados
Fecha de actualización: 15 de abril de 1999