Automatas

Instituto Profesional Diego Portales
Ingeniería en Informática





AUTÓMATAS FINITOS BIDIRECCIONALES






ALUMNO: Srta. Torres Núñez Paz A.
PROFESOR: Señor Farías Alexis.






SANTIAGO - JULIO - 2010



































INTRODUCCIÓN

Los autómatas Finitosbidireccionales, si bien reconocen la misma familia de lenguajes que los unidireccionales, permiten en muchos casos simplificar notablemente su diseño. En esta investigación se pondrá de manifestó la existencia de numerosos lenguajes para los cuales se hace difícil encontrar directamente autómatas finitos unidireccionales que los reconozcan. En cambio, se verá que para estos mismos lenguajes es muyfácil diseñar autómatas bidireccionales. La construcción posterior de un autómata unidireccional equivalente quedará entonces como un procedimiento mecánico, aunque pueda ser complejo.

Autómatas Finitos Bidireccionales

Un autómata finito determinista bidireccional (abreviadamente un 2dfa, del inglés 2-way Deterministic finite automaton) es una estructura de la forma

en que tienen elsignificado habitual de conjunto finito de estados, alfabeto de entrada, estado inicial y conjunto de estados aceptadores, respectivamente. También aquí Delta designa una función de transición, que ahora es de la forma

El funcionamiento de los autómatas bidireccionales es el siguiente. Inicialmente el autómata esta en el estado q0 y tiene el cabezal situado delante del primer símbolo de la Izquierda dela palabra de entrada. Supongamos que en un momento determinado el Autómata se encuentra en un estado p y el símbolo que hay delante del cabezal es a.

Supongamos también que la función de transición toma el valor. En estas condiciones, el autómata pasa del estado p al estado q, y mueve el cabezal una posición a la izquierda o a la derecha según que m valga i o d, respectivamente.

Observemosque un DFA de los estudiados hasta ahora, y que aquí llamaremos unidireccional, puede ser interpretado como un caso particular de un 2dfa en el que todos los valores de la función de transición son de la forma (q; d).
En tal caso, solo el valor del nuevo estado q es relevante, y sabemos que solo hay una extensión posible de la función al dominio . En cambio, en el caso general de los 2dfas, notiene sentido considerar una extensión de este tipo. Designemos por la primera de las dos componentes de la función , es decir la que define el cambio de estado. Supongamos que extendiésemos esta función a palabras de manera que (p;w) fuese el estado en que se encontraría el autómata cuando el cabezal saliese por la derecha después de procesar la palabra w partiendo del estado p y del cabezalsituado en la primera posición de w. (Podríamos considerar que los casos en que el cabezal sale por la izquierda de w o aquellos en que el autómata entra en bucle a medio leer w, dan lugar a una transición a un estado pozo). No podríamos establecer la igualdad entre (p; xy) y ( (p; x); y), ya que pueden darse situaciones del tipo


en que el comportamiento de (q; y) depende del prefijo queprecede y, y no solo del estado q. Con el fin de describir la situación a que se llega tras efectuar un número cualquiera de pasos, introduciremos el concepto de configuración o descripción instantánea. Supondremos, sin pérdida de generalidad, que no tienen símbolos en común. Definimos el conjunto KM de configuraciones así:

Es frecuente admitir una tercera posibilidad, a saber, que el cabezalquede inmóvil. Es fácil ver que esta modificación del modelo no afecta al conjunto de los lenguajes reconocidos.

Hasta ahora los autómatas que hemos considerado leen su entrada de izquierda a derecha y no reculan sobre ella para realizar transiciones alternativas en función de la “historia'' de la entrada. Los autómatas bidireccionales en cambio, sí pueden revisar la cadena de entrada y...