Automatas finitos

AUTÓMATAS FINITOS DETERMINISTAS


Un autómata finito determinista (abreviado AFD), denominémoslo M, es una máquina teórica que se utiliza para reconocer cadenas de un lenguaje regular, llamémoslo L. Se puede describir como una quíntupla, así:

M= (S, Σ, δ, t, F), donde,

S es un conjunto finito de estados.
Σ es el alfabeto de la máquina (el conjunto de símbolos con los que se conformanlas cadenas del lenguaje L).
δ es la función de transición, definida así:

δ : (Sx Σ) Σ . A cada par (estado, símbolo) se asigna UNO Y SOLO UN siguiente estado.

t Є S, es el estado de inicio
F S son los estados de aceptación.

Los autómatas finitos (deterministas o no), se pueden representar como un diagrama de transiciones ( un grafo dirigido), o sea conestados y transiciones entre estados, tal como lo ilustra el siguiente

EJEMPLO: Sea L un lenguaje del Σ = {0,1} de aquéllas cadenas que comienzan por 0 y terminan en 1.

L = { ω | ω comienza con 0 y terminan con 1} – (Esto es una definición por comprensión del lenguaje L) -

La siguiente figura corresponde a un AFD que reconoce L ( es decir, que acepta todas las cadenas de L y solo las deL).
DIAGRAMA DE TRANSICIONES DEL AFD QUE RECONOCE L [pic]
Para el ejemplo anterior el modelo formal es:

M= (S, Σ, δ, t, F), donde:

S = {A,B,C,X}, el conjunto de estados de M

Σ = {0,1}, el alfabeto de la máquina.

δ es la función de transición: (en el autómata son los arcos dirigidos), cada arco tiene asociado un símbolo de Σ

δ(A,0)=B
δ(A,1)=X
δ(B,0)=Bδ(B,1)=C
δ(C,0)=B
δ(C,1)=C
δ(X,0)=X
δ(X,1)=X

t= A, el estado inicial, se distingue por tener una flecha que apunta a él sin que haya un estado anterior

F={C} es el subconjunto de estados de aceptación. Se distinguen con doble círculo en el autómata.


Al lenguaje L, reconocido por el autómata M se le denomina:

L(M)

Las letras dentro de los estados sonnombres escogidos arbitrariamente.


CÓMPUTOS QUE REALIZA EL AUTÓMATA M

El autómata opera sobre una cinta de entrada que contiene tantas celdas como símbolos tenga la cadena a analizar. Cada símbolo en una celda. La cinta de entrada dispone de una cabeza de lectura.

Arrancando en el estado inicial, y con el primer símbolo de la cadena (el del extremo izquierdo), se aplica la función detransición así:

Dado el estado actual (que al principio siempre debe ser el estado inicial del autómata), y el símbolo actual de cinta, (el que está siendo apuntado al momento por la cabeza de lectura), se determina el siguiente estado mediante la función de transición. Se toma la transición que corresponda con el símbolo actual de cinta y se avanza en ésta a la siguiente posición. Tenemos así unsiguiente estado un siguiente símbolo actual de cinta. Al terminar la cadena, ésta será aceptada por el autómata si el último estado que alcanzó es un estado de aceptación y se rechaza en caso contrario.

Definición: Los lenguajes que son reconocidos por un autómata finito , determinista o no, se llaman LENGUAJES REGULARES.


AUTÓMATAS FINITOS NO DETERMINISTAS


Un autómata finito nodeterminista es aquel en el cual desde alguno de sus estados se origina más de una transición con un mismo símbolo. Veamos un ejemplo.

Sea el alfabeto Σ = {0,1} y el siguiente lenguaje:

L1= {ω | termina en 0}

Un autómata finito no determinista: M1.1 que reconoce el lenguaje L1 es:



M1.1



Observe que desde el estado A se originan dos transiciones con el símbolo 0: una llega en Amismo y la otra llega al estado B. Este autómata, por lo tanto, no es determinista. Se llama así por cuanto no está determinado de manera única el siguiente estado desde A con 0.

Todo autómata finito no determinista tiene un equivalente determinista, veamos el autómata finito determinista M1.2 para L1 :




M1.2





Observe que los dos autómatas M1.1 y M1.2 reconocen las mismas...