UNIDAD 3

3. Automatas Finitos

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por un alfabeto, un conjunto de estados finito, una función de transición, un estado inicial y un conjunto de estados finales. Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

3.1  Conceptos: Definición y Clasificación de Autómata Finito (AF).

Un autómata finito o máquina de estado finito es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el autómata reconoce.

Éstos se definen mediante una quíntupla (E, Q, f, q0, F ) donde:

E: alfabeto de entrada.

Q: conjunto de estados; es conjunto finito no vacío.

f: función de transición. f(p,a)=q

q0 : (perteneciente a Q) estado inicial.

F : (perteneciente a Q) conjunto de estados finales o de aceptación.

Clasificacion

Los autómatas se pueden clasificar en:

-       Deterministas

Cada combinación (estado, símbolo de entrada) produce un solo estado.

-       No Deterministas

Cada combinación (estado, símbolo de entrada) produce varios estados y además son posibles las transiciones con λ.

Representacion

Los autómatas se pueden representar mediante tablas de transición o diagramas de transición.

Tablas de transición:

• Filas encabezadas por los estados( Q )

• Columnas encabezadas por los símbolos de entrada ( E )

Diagramas de transición:

• Nodos etiquetados por los estados(Q)

• Arcos entre nodos etiquetados con ( E )• Q0 se señala con ->• El estado final se señala con * o con doble circulo

definida por:

f(p,a) = q f(p,b) = r

f(q,a) = q f(q,b) = r

f(r,a) = r f(r,b) = r

escribir su tabla de transición y dibujar su diagrama de transición.
estados (Q): p, q, r

estado inicial: p

estado final: q

símbolos: a,b

3.2  Conversión de un Autómata Finito No  Determinista (AFND) a  Autómata  Finito

Transformación de autómata finito no determinista a autómata finito determinista. Todo AFND estricto, o sea un AFND que no es AFND-V, puede ser transformado a AFD utilizando un algoritmo que transforma los estados del AFND en nuevos estados que son subconjuntos de los estados originales y aplica a los mismos la clausura para confirmar la conexidad entre cada uno de los componentes y así eliminar el indeterminismo.

Este algoritmo aunque siempre obtiene un AFD equivalente no puede decirse que sea la versión minimal del mismo, para ello deben aplicarse otras transformaciones.

Algoritmo

Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q₀>, donde Q es el conjunto de estados, Tel alfabeto de símbolos terminales, la relación de transiciones  ó  (léase: del estado q_imediante el terminal x se va a q_j), F son los estados finales o de llegada dentro de Q, q₀ es el estado inicial o de partida

1.   A se transforma en A_AFD=<Q_A,T, g_A,F_A,q_0A>', tal que:

1.  V_A=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.

2.  F_A={x | }.

3.  g_A={<r,x,q> | }.

4.  q_0A={q₀}.

2.   Luego se eliminan de A_AFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q_0A.

Véase el proceso de transformación de AFND a AFD del autómata A=<{q0,q1,f},{a,b},{<q0,a,q0>,<q0,b,q0>,<q0,a,q1>,<q1,b,f>},{f},q0>, que reconoce a las cadenas de as y bs que comienzan con cualquiera cantidad de estas letras y terminan forzosamente en ab. El siguiente puede ser su diagrama de estados:

Primero se obtiene autómata derivado A_AFD=<V_AFD,T_AFD,g_AFD,F_AFD,{q0}> a partir del conjunto potencia de los estados de A donde:

     V_AFD={{q0},{q1},{f},{q0,q1},{q0,f},{q1,f}, {q0,q1,f}}.

     T_AFD={a,b}.

     F_AFD={{f},{q0,f},{q1,f}, {q0,q1,f}}.

Cuyo diagrama sería:

3.3 Representación de ER usando AFND

Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de éstos -autómatas finitos-. Es posible dada una expresión regular obtener el AFD que reconozca las cadenas del lenguaje denotado por la expresión regular. También es posible obtener el AFND que reconozca el lenguaje representado por dicha expresión regular. El algoritmo que permite construir el autómata finito determinístico está fuera del alcance de estas notas ( el alumno no tiene los prerrequisitos para su estudio en este curso). Sin embargo, el algoritmo utilizado para la construcción del autómata finito no determinístico AFND, es relativamente sencillo de aplicar, ya que se basa en reglas simples. Existen muchas variantes de este algoritmo denominado “Algoritmo de Thompson”. 

Este algoritmo es dirigido por sintaxis, es decir, usa la estructura sintáctica de la expresión regular para guiar el proceso de construcción del autómata AFND. 

Supongamos que N(s)y N(t)son AFND’s para las expresiones regulares sy t, respectivamente. 

a) Para la expresión regular s | t(alternancia), construir el siguiente AFND, N(s|t): 

b) Para la expresión regular st(concatenación), construir el AFND,N(st) 

c) Para la expresión regular s*, construir el AFND,N(s*)

3.4 Minimización de un AFD

Dos estados de un autómata finito determinista son estados equivalentes si al unirse en un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesen separados. Esta unión de estados implica la unión tanto de sus transiciones de entrada como de salida. Si dos estados no son equivalentes, se dice que son estados distinguibles. Un estado final con un estado no-final nunca serán equivalentes.

Un AFD está minimizado, si todos sus estados son distinguibles y alcanzables. Un algoritmo de minimización de AFD es el siguiente:

1. Eliminar los estados inaccesibles del autómata.

2. Construir una tabla con todos los pares (p, q) de estados restantes.

3. Marcar en la tabla aquellas entradas donde un estado es final y el otro es no-final, es decir, aquellos pares de estados que son claramente distinguibles.

4. Para cada par (p, q) y cada símbolo a del alfabeto, tal que r = δ(p,a) y s = δ(q,a):

Si (r, s) ya ha sido marcado, entonces p y q también son distinguibles, por lo tanto marcar la entrada (p, q).

De lo contrario, colocar (p, q) en una lista asociada a la entrada (r, s).

5. Agrupar los pares de estados no marcados.

Ejemplo

En la primera figura del ejemplo, se muestra un autómata con el estado inaccesible d, el cual puede eliminarse inmediatamente. Luego se construye la tabla de pares de estados, y a continuación se marcan, de acuerdo a la tercera línea del algoritmo, las filas y columnas correspondientes a los estados finales c y g, salvo la celda que representa el par (c,g), puesto que al ser ambos estados finales, pueden ser estados equivalentes. Posteriormente, se marcan las celdas restantes de acuerdo a la cuarta línea del algoritmo, notando que el par (b, f) queda asociado con el par (c, g), y así finalmente se obtiene el autómata final, agrupando los estados b y f, así como c y g, tal y como se muestra en la segunda figura del ejemplo.

3.5  Aplicaciones (definición de un caso de estudio).

Construcción del vehículo evasor de obstáculos Uno de los primeros trabajos que comenzaron a formalizar la dinámica de robots móviles es (Crowley, 1989) en el que se utilizan dispositivos ultrasónicos en el vehículo para su posicionamiento y orientación. 

En (Maes, 1990) se muestra un estudio del comportamiento de robots autónomos y se divide en construcción de mapas, exploración, transitar y evasión de obstáculos. 

En (Seng, 1997) se plantea como una de las mayores problemáticas de la navegación robótica la localización y se proponen los pasos claves para el diseño, calibración y modelado de autómatas. Hay otros autores que refuerzan la evasión de objetos o desarrollo de trayectorias mediante técnicas de navegación como son: navegación inercial, compases magnéticos y triangulación. (Borenstein, 1997). 

(Betke, 1997) considera que el autómata puede reconocer marcas especificas en el medio por el cual se desplaza usando reconocimiento de patrones visuales. La localización robótica así como la evasión de obstáculos del autómata, ha llegado a ser uno de los problemas fundamentales en los robots móviles, y por ello, en (Fox, 1999) se presenta una versión de la localización Markov, en donde la idea principal es mantener una densidad de probabilidad sobre el espacio de todas las localizaciones posibles de un robot en su entorno.