1.2. AUTÓMATAS FINITOS DETERMINISTAS. MÁQUINA CONCEPTUAL
1.2.1. Definiciones básicas
Alfabeto.- conjunto de símbolos finito no vacío a partir del cual estarán construidas las cadenas.
Flujo de entrada.- Cada cadena se va a presentar como una secuencia de símbolos analizándose de uno en uno y de izquierda a derecha. Esta secuencia puede llegar a ser infinita.
Cuando llega un símbolo del flujo de entrada, este se reconoce si se cambia de un estado a otro o bien se permanece en el mismo, si la transición (arco etiquetado) es posible con ese símbolo. El nuevo estado dependerá únicamente del estado actual y del símbolo que se recibe.
Un autómata finito determinista consiste en un dispositivo que puede estar en un estado de entre un número finito de los mismos; uno de ellos será el estado inicial y por lo menos uno será estado de aceptación. Tiene un flujo de entrada por el cual llegan los símbolos de una cadena que pertenecen a un alfabeto determinado. Se detecta el símbolo y dependiendo de este y del estado en que se encuentre hará una transición a otro estado o permanece en el mismo. El mecanismo de control (programa) es que determina cual es la transición a realizar.
La palabra finito se refiere a que hay un número finito de estados.
La palabra determinista es porque el mecanismo de control (programa) no debe tener ambigüedades, es decir, en cada estado solo se puede dar una y solo una (ni dos ni ninguna) transición para cada símbolo posible (en el ejemplo anterior, la tabla de transiciones era determinista en ese caso, no así el diagrama, aunque podría serlo como veremos mas tarde).
El autómata acepta la cadena de entrada si la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena. Si después del último símbolo la máquina no queda en estado de aceptación, se ha rechazado la cadena.
Si la máquina llega al final de su entrada antes de leer algún símbolo la entrada es una cadena vacía (cadena que no contiene símbolos) y la representaremos con l. Solo aceptará l si su estado inicial es de aceptación.
1.2.1.1 Definición formal
Un autómata finito determinista consiste en una quíntupla (S, S, d, i, F) donde:
- S es un conjunto finito de estados
- S es el alfabeto de la máquina
- d es una función (llamada de transición) de S x S en S ( d:( Sx S)® S)
- i (un elemento de S) es el estado inicial
- F (un subconjunto de S) es el conjunto de los estados de aceptación.
Dados dos estados, p y q, de S y cualquier elemento del alfabeto, x de S, la función transición es d (p,x)=q si y solo si se puede pasar de un estado p a uno q al leer el símbolo x. Más formalmente, el autómata (S, S,d ,i,F) acepta la cadena no vacía de la forma x1x2...xn si y solo si existe un camino a través de una serie de estados s0,s1,...sn tal que s0=i (uno es inicial) y snÎ F (al menos uno es de aceptación) y para cada entero j de 1 a n, y cada símbolo x del alfabeto, se da la función d (sj-1,xj)=sj.
1.2.2. Diagrama de transiciones determinista
Estará caracterizado porque debe estar totalmente definido: para cada estado solo debe salir un arco y solo uno para cada símbolo (el autómata no puede determinar la transición en el caso de que haya dos arcos con el mismo símbolo o no haya ninguno).
Para convertir un diagrama de estados no determinista (que tenga uno o ningún arco por cada símbolo del alfabeto en cada estado) en uno que lo sea se deben seguir los siguientes pasos (luego se verán los diagramas con dos o ningún arco por símbolo):
- 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 cadena no aceptable hará que la máquina llegue al estado de captación global y allí permanece hasta el FDC. Como este estado no es de aceptación, se rechaza la cadena.
En la práctica, si se dibujan todas las transiciones posibles, se puede llegar a saturar el diagrama(no se ve realmente que hace el autómata); para evitarlo se dibujan versiones parciales de los diagramas de transiciones deterministas.
1.2.3. Tabla de transiciones determinista
La tabla de transiciones tal y como se definió con anterioridad se puede hacer que sea determinista, exigiéndole que admita "error" sólo en la columna FDC (aparte de aceptar, que debe existir).
© 1999 Roberto de la Fuente López. Todos los derechos reservados
Fecha de actualización: 14 de abril de 1999