Bloque 3 Autómatas 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 y un conjunto de transiciones entre dichos estados. 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 Definición formal Autómata Finito

 Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:

 es un conjunto finito de estados; 

 es un alfabeto finito; 

 es el estado inicial; 

 es una función de transición; 

 es un conjunto de estados finales o de aceptación. 

En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata finito se encuentra en el estado inicial y a medida que procesa cada símbolo de la cadena va cambiando de estado de acuerdo a lo determinado por la función de transición. Cuando se ha procesado el último de los símbolos de la cadena de entrada, el autómata se detiene en el estado final del proceso. Si el estado final en el que se detuvo es un estado de aceptación, entonces la cadena pertenece al lenguaje reconocido por el autómata; en caso contrario, la cadena no pertenece a dicho lenguaje.

Note que el estado inicial de un autómata finito siempre es único, en tanto que los estados finales pueden ser más de uno, es decir, el conjunto puede contener más de un elemento. También puede darse el caso de que un estado final corresponda al mismo estado inicial.

3.2 Clasificación de Autómata Finito

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 λ. 

3.3 Conversión de un AFND a AFD 

Para convertir un AFD en un AFN que reconozca el mismo lenguaje. Este algoritmo, a menudo es llamado construcción de subconjuntos, es útil para simular un AFN por medio de un programa de computadora.

En la tabla de transiciones de un AFN, cada entrada es un conjunto de estados; en la tabla de transiciones de un AFD, cada entrada es tan solo un estado. La idea general tras la construcción AFN a AFD es que cada estado de AFD corresponde a un conjunto de estados del AFN. El AFD utiliza un estado para localizar todos los posibles estados en los que puede estar el AFN después de leer cada símbolo de la entrada. Es decir, después de leer la entrara a1, a2,. ..an, el AFD se encuentra en un estado que representa al subconjunto T de los estados del AFN alcanzables desde el estado de inicio del AFN a lo largo de algún camino etiquetado con a1, a2,. ..an. El número de estados de AFD puede ser exponencialmente en el número de estados del AFN pero en la práctica este peor caso ocurre raramente. 

Algoritmo (Construcción de subconjuntos) Construcción de un AFD a partir de un AFN. 

Entrada. Un AFN N 

Salida. Un AFD D que acepta el mismo lenguaje 

Método. El algoritmo construye una tabla de transiciones tranD para D. Cada estado del AFD es un conjunto de estados del AFN y se construye tranD de modo que D simulará "en paralelo" todos los posibles movimientos que N puede realizar con una determinada cadena de entrada.

Se utilizan las operaciones de la siguiente tabla para localizar los conjuntos de los estados del AFN (s representa un estado del AFN, y T un conjunto de estados del AFN). 

Antes de detectar el primer símbolo de entrada N se puede encontrar en cualquiera de los estados del conjunto cerradura- (S0), donde S0 es el estado de inicio de N. Supóngase que exactamente los estados del conjunto T son alcanzables desde S0 con una secuencia de símbolos de entrada, y sea a el siguiente símbolo de entrada. Al ver a, N puede trasladarse a cualquiera de los estados del conjunto mueve(T, a). Cuando se permiten transicionesencontrarse cualquiera de los estados de cerradura- (T, a), después de ver la a. 

Se construyen estadosD, el conjunto de estados de D, y tranD, la tabla de transiciones de D, de la siguiente forma. Cada estado de D corresponde a un conjunto de estados de AFN en los que podría estar N después de leer alguna secuencia de símbolos de entrada, incluidas todas las posibles transicionesanteriores o posteriores a la lectura de símbolos. El estado de inicio de D es cerradura- S0). Se añaden los estados y las transiciones a D utilizando el algoritmo siguiente. Un estado de D es un estado de aceptación si es un conjunto de estados de AFN que contenga al menos un estado de aceptación de N.

al inicio, cerradura- 0) es el único estado dentro de estadosD y no está marcado; while haya un estado no marcado T en estadosD do begin marcar T; for cada símbolo de entrada a do begin U:= cerraduraif U no está en estadosD then añadir U como estado no marcado a estadosD; tranD[T, a]:= U; end; end; El cálculo de cerradura- (T) es un proceso típico de búsqueda en un grafo de nodos alcanzables desde un conjunto dado de nodos. En este caso, los estados de T son el conjunto dado de nodos. En este caso, los estados de T son el conjunto dado de nodos, y el grafo está compuesto solamente por las aristas del AFN etiquetadas por.

Ejemplo: 

La siguiente figura muestra otro AFN N aceptando el lenguaje (a | b)*abb. Se aplica el algoritmo anterior a N. El estado de inicio del AFD equivalente es cerradura- , que es A = {0, 1 , 2, 4, 7 }, puesto que estos son exactamente los estados alcanzables desde el estado 0 un camino puede no tener aristas, de modo que 0 es alcanzado desde sí mismo por dicho camino. Aquí, el alfabeto de símbolos de entrada es {a, b}. El algoritmo anterior indica que hay que marcar A y después calcular cerradura- . Primero se calcula mueve (A, a), el conjunto de estado de N que tiene transiciones en a desde miembros de A. Entre los estados 0,1,2,4 y 7 sólo 2 y 7 tienen dichas transiciones, a 3 y a 8, de modo que: cerradura- - Este conjunto se denominará B. Así, tranD[A,a] = B. Entre los estados de A, solo 4 tienen una transición en b a 5, de modo que el AFD tiene una transición en b desde A a C = cerradura- Por tanto, tranD[A,b] = C Si se continua este proceso con los conjuntos B y C, ahora sin marcar, finalmente, se llegará al punto en que todos los conjuntos que son estados del AFD estén marcados. Esto es cierto porque "solo" hay 211 subconjuntos distintos de un conjunto de 11 estados, y un conjunto, una vez marcado, queda marcado para siempre. 

Los cinco conjuntos de estados realmente construidos son:

A = {0,1,2,4,7 } 

B = {1,2,3,4,6,7,8 }

C = {1,2,4,5,6,7 } 

D= {1,2,4,5,6,7,9 }

E= {1,2,4,5,6,7,10 }

El estado A es el estado de inicio, y el estado E es el único estado de aceptación. La tabla de transiciones completa tranD se muestra a continuación. Estado Símbolo de entrada a b A B C B B D C B C D B E E B C 

En la siguiente figura, se muestra un grafo de transiciones para el AFD resultante. 

3.4 Representación de ER usando AFND

ERs, AFDs y AFNDs son mecanismos equivalentes para denotar los lenguajes regulares. En

estas tres secciones demostraremos esto mediante convertir ER →AFND → AFD → ER. Las

dos primeras conversiones son muy relevantes en la práctica, pues permiten construirverificadores o buscadores eficientes a partir de ERs.

3.4

Definición 

: La función Th convierte ERs en AFNDs según las siguientes reglas.

Prueba 

: Es fácil verificarlo por inspección y aplicando inducción estructural. La única parteque puede causar problemas es la clausura de Kleene, donde otros esquemas alternativos que podrían

 sugerirse (por ejemplo M = (K1, Σ, ∆1

∪ 

{(f1, ε, s1), (s1, ε, f1)}, s1, {f1}) tienen el

 problema de permitir terminar un recorrido de Th(E1) antes de tiempo. Por ejemplo el ejemploque acabamos de dar, aplicado sobre E1 = a

⋆ 

 b, reconocería la cadena x = aa

Existen algoritmos que relacionan la especificación de tokens -expresiones regulares-, con el reconocimiento de estos -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

3.5 Minimización de estados en un AF 

Dos estados de un autómata finito determinista son estados equivalentes si al unirseen un sólo estado, pueden reconocer el mismo lenguaje regular que si estuviesenseparados. Esta unión de estados implica la unión tanto de sus transiciones de entradacomo de salida. Si dos estados n o son equivalentes, se di ce que son estadosdistinguibles. Un estado final con un estado no- final nunca serán equivalentes.

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

Eliminar los estados inaccesibles es 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):

1.

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

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

Agrupar los pares de estados no marcados.Luego del tercer paso, si la tabla creada queda completamente marcada, entonces el AFDinicial ya era mínimo. La complejidad computacional del problema de minimizar u n AFD es polinomio. De hecho, existen algoritmos más eficientes aún que el mostrado en este artículo(aunque menos intuitivos). Sin embargo, el problema de minimizar un autómata finito nodeterminista es NP- completo y PSPACE- completo.

3.6 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 ultra só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.

El Vehículo Evasor de Obstáculos (VEO de aquí en adelante) obtiene información del medio por el cual transita a través de unos foto diodos y unas foto resistencias que actúan como sensores, estos sensores arrojan como resultado niveles de voltaje que varían en proporción directa con la proximidad al obstáculo, los niveles de voltaje después de pasar por un comparador de niveles se convierten en niveles digitales, los cuales determinan una dirección especifica al actuar como entradas en el bus de direcciones de una memoria RAM, la cual se ha cargado con un programa, que contiene instrucciones precisas para lograr la evasión de obstáculos, estas instrucciones que provienen del bus de datos de la memoria RAM, controlan directamente 2 dispositivos transistor izados conocidos como puentes H, los cuales interactúan directamente con los motores de dirección del vehículo, indicándoles la acción de giro y por tanto ejecutando los diferentes movimientos para los cuales se diseño VEO.

Es necesario por tal motivo presentar el programa que se cargo en la memoria RAM según (Catálogo,2010), lo cual representa el punto de partida para definir el alfabeto que se emplea para la descripción de la dinámica de VEO a través de autómatas finitos.En la figura 5 se puede observar la apariencia física del vehículo evasor de obstáculos.