Automatas

AUTÓMATAS FINITOS DETERMINISTICOS

(AFD)

Una máquina de estado finito se utiliza para representar expresiones regulares. Para entender su funcionamiento es conveniente familiarizarnos con algunos conceptos de la simbología formal y hacer la relación con un grafo. Una máquina de estados finitos es un quíntuplo en el cual se señalan el alfabeto y la función de traslación entre estados. La transición es única, ya que de cada estado salen exactamente el número de elementos del alfabeto.

Estos autómatas no tienen almacenamiento temporal. Debido a que el número de estados es finito, un AFD puede tratar únicamente con situaciones en las cuales la información a ser almacenada en determinado tiempo está estrictamente limitada. Para representar estos autómatas, usamos grafos de transición, en los cuales los vértices representan los estados y las ligas las transiciones. Un lenguaje es el conjunto de cadenas aceptadas por un Autómata.

Se requiere mostrar la teoría de grafos, a manera de recordatorio, ya que éste es un tema de la asignatura de Matemáticas Discretas.

Es una herramienta útil para generar palabras pertenecientes a un lenguaje determinado son las expresiones regulares. Ahora nos gustaría tener otra herramienta, que dado un lenguaje y una cierta cadena, podamos determinar con certeza si ella pertenece o no al lenguaje. La herramienta más básica que usaremos para ello son los AFD, cuyo funcionamiento se basa en ir leyendo caracteres desde una cinta que contiene caracteres en un alfabeto.

Cada vez que la maquina lee un caracter desde la cinta, cambia a un estado nuevo que depende del estado anterior. Si al leer el ultimo caracter de la cinta, el autómata quedó en un estado perteneciente al conjunto de estados finales, entonces la cadena pertenece al lenguaje asociado al autómata. (la definición formal ya fué vista en clases).

Al hablar sobre el lenguaje asociado a un autómata, estamos intuitivamente afirmando que todos los autómatas tienen un lenguaje asociado. Esto es cierto, y para cada expresión regular podremos encontrar un autómata que reconozca todas las palabras que la expresión genera y viceversa.

Sin embargo, un Lenguaje no está asociado a un único autómata. Es más, a un mismo lenguaje le podemos asociar siempre muchos autómatas que reconocen las cadenas en él.

El recíproco sin embargo no es cierto: un autómata reconoce uno y solo un lenguaje.

Aceptación de una palabra

Cuando rastreamos el AFD, nos damos cuenta que la cantidad de caminos desde un estado se reduce al número de elementos del alfabeto. Por lo tanto hay que concentrarnos en las configuraciones convenientes para armar un buen autómata. Muchas veces hacemos autómatas redundantes, y aunque aceptan las palabras requeridas, no son óptimos y eso se manifiesta en la implementación del AFD por computadora.

Una máquina de estados finitos es un quíntuplo (K, , ,s, F ), donde

K es un conjunto de identificadores de estados

 es el alfabeto de entrada

s  K es el estado inicial

F  K es un conjunto de estados finales

: Kx  K es la función de transición

Una configuración es la situación en que se encuentra la máquina en un momento dado.

Definición. [q1,w1 M [q2,w2 ssi w1=w2 para un   , y existe una transición en M tal que

 (q1, )=q2

Definición. Una palabra w  * es aceptada por una máquina M=(K, , ,s, F ) ssi existe un estado

q  F tal que [s,w M* [q, 

Definición. Un cálculo en una máquina M es una secuencia de configuraciones c1,c2,...,cn tales que ci  ci+1.

Teorema. Dados una palabra w  * y una máquina M, sólo hay un cálculo

[s,w M... M[q,  .

Definición. Dos autómatas M1 y M2 son equivalentes, M1  M2 , cuando aceptan exactamente el mismo lenguaje.

Definición. Dos estados son compatibles si ambos son finales o ninguno es final.

Definición. Dos estados q1 y q2 son equivalentes, q1  q2 , ssi al intercambiarlos en cualquier configuración, no se altera la aceptación o rechazo de toda palabra.

Definimos una función  de Kx*  K de la siguiente manera

(q,)

(q,wa) = ( (q,w), a )

La intención es que (q,w) represente al estado en que estará el AF después de leer la cadena w del estado q.

Existen algunas características interesantes en un AFD que es conveniente analizar. Por ejemplo, el número de transiciones que salen de cada estado está en función de los elementos del alfabeto. Esta característica parece dificultar la representación regular del autómata, pero la definición lo pide, por lo cual, el alumno deberá pensar un poco más antes de obtener el AFD definitivo.

Una palabra es reconocida por un AFD cuando se realizan una serie de configuraciones hasta llegar a un estado final y la cadena haya sido consumida en su totalidad.

Cuando se rastrea una palabra en un AFD, se conocen los estados por donde se va pasando; sin embargo este camino es único, ya que de cada estado solo sale una transición por cada elemento del alfabeto. El alumno deberá demostrar esta unicidad, reforzando con aplicaciones. El cálculo de una palabra en un AFD es único.

ELABORANDO UN AFD

La construcción de AFD’s es esencial para entender el comportamiento de las expresiones regulares. Dado un alfabeto y una serie de condiciones, se puede elaborar un AFD que satisfaga dichas condiciones, mediante ensayo y error

Ejercicios

Dado el alfabeto en {0,1}, elaborar un AFD que acepte solamente palabras

a) que empiecen con 00

b) que no empiecen con 00

c) con un número par de ceros

d) con un número impar de unos

e) con las dos condiciones anteriores

A continuación se realiza el inciso c:

Las palabras reconocidas son todas aquellas que llegan a los estados finales a partir del estado inicial. Un autómata finito (determinista) es pues una estructura de la forma

donde

Un semiautómata finito es una estructura de la forma

Es decir, es un ``autómata finito'' en el que no se ha especificado estados finales. Todo autómata finito puede ser visto

...