Autómatas Finitos

Autómatas Finitos Deterministas

Se llama Autómata Finito Determinista (AFD) a la quíntupla:

(å , Q, f, q₀, F)

• å es un alfabeto, llamado "alfabeto de entrada".
• Q es un conjunto finito, no vacío llamado "conjunto de estados".
• f es una función f: Qxå ® Q que se llama "función de transición".
• q_0Î Q es el "estado inicial".
• FÌ Q es el conjunto de "estados finales", o "estados de aceptación", no vacío.

Un AFD puede considerarse como una máquina secuencial de Moore, cuyo alfabeto de entrada sea å , su alfabeto de salida å _S={ 0,1} , y donde F será el conjunto de los estados tales que g(q)=1.

 

Tabla de Transición

Será una tabla cuyas filas están encabezadas por los estados (elemen-tos de Q). Los encabezamientos de las columnas son los símbolos del alfabeto de entrada (los elementos de å ). Cumpliéndose que el elemento i, j de la tabla de transición corresponde al valor de f(q_i, e_j), donde q_i es el elemento i-ésimo de Q, y e_j es el elemento j-ésimo de å . Tanto el estado inicial como el final estarán marcados por ® y por * respectivamente. Nota: el estado final puede ser indicado también rodeando el estado por un círculo.

 

	(å ): a1...an
® q0 ..... qi ...... *qf

Ejemplo:

AF=({ 0,1} ,{ q₀,q₁,q_2} , f, q₀, { q_1} )

f	0	1
® q0	q1	q0
*q1	q0	q2
q2	q1	-

Diagrama de Transición

Es un grafo dirigido que se forma de la siguiente manera:

1. El grafo tendrá tantos nodos como | Q| , cada nodo estará etiquetado por un elemento de Q.

1. Si f(q_i, e_j) = q_k, dibujaremos una rama dirigida desde el nodo de etiqueta q_i hasta el nodo de etiqueta q_k. La etqueta de la rma será e_j.
2. El estado inicial estará señalado mediante el símbolo ® .
3. Los estados finales estarán señalados mediante el simbolo *, o doble círculo alrededor de la etiqueta del estado final.

Representamos los estados como:

Ejemplo: (partiendo del autómata anterior)

Lenguaje asociado a un autómata finito determinista L(AFD)

Sea un AFD (å , Q, f, q₀, F). Decimos qie una palabra x Î å * es "aceptada" o "reconocida" por el autómata si f(q₀,x) Î F. Se llama lenguaje asociado al autómata finito, o conducta del autómata finito al conjunto de todas las palabras aceptadas por éste. Es decir: L = { x | xÎ å * & f(q₀,x)Î F}

Ejemplo:

0 Î L(AF), ya que f(q₀, 0) = q₁ Î F

10 Î L(AF)

1*0 Î L(AF)

1*010 Î L(AF)

Luego L(AF) = 1*0(10)*

Ejemplo 2 :

Calculo posibles caminos desde q₀ a q₀ (por ser el estado inicial): (1*+(10)*0)*

Caminos desde el estado inicial hasta el estado final (el mas corto): 0

Caminos desde el estado final al estado final sin pasar por el inicial: (10)*

Luego L(AF)= (1*+(10)*0)* 0 (10)*

 

Estado Accesible

Un estado de un AF es accesible si existe una palabra x que permite que el autómata se pare en ese estado partiendo del estado inicial. Es decir, un estado q es accesible desde otro estado p del autómata si existe una cadena x que permite que el autómata transitando desde p con x se pare en el estado q:

qÎ Q es accesible si $ x | x Î å * | q = f(q₀, x)

Por definición de función de transición, todo estado es accesible desde sí mismo, y es accesible mediante la palabra vacía.

 

LEMA del estado accesible

Dado un AF que tiene n estados, |Q|= n, un estado qÎ Q es accesible desde otro estado p si y sólo si $ xÎ å * | |x|<n (siendo n el nº de estados de autómata) | f(p,x)=q.

Supongamos |x|>=n | f(p,x=q Þ siempre es posible escontrar otra cadena x’Î å * | |x|<n | f(p,x’)=q.

Es decir, que si yo tengo un autómata con n estados, si transito por todos los estados, pasando una vez por cada estado, habré realizado n-1 transiciones, que es menos que n estados.

Si |x|>=n para la transición se repetirá al menos un estado.

Ejemplo :

 

 

q₂ es accesible desde q₀, por ejemplo con la palabra: x=110001, |x|=6, como |Q|=3, decimos que siempre podremos encontrar una palabra x’ tal que |x’|<|x| (puesto que |x|>|Q|)

y ademá cumple que |x’|<|Q|. Esta x’ sería: x’=01

Autómatas conexos

Sea (å , Q, f, q_o, F) un autómata finito determinista. Diremos que el autómata es "conexo" si todos los estados de Q son accesibles desde el estado inicial q_o.

Dado un autómata no conexo, podemos obtener a partir de él otro autómata que sea conexo eliminando todos los estados que no sean accesibles desde qo. Es evidente que los dos autómatas aceptarán el mismo lenguaje.

Ejemplo: sea el autómata definido por el diagrama de transición siguiente:

Es evidente que los estados q y s son inaccesibles desde el estado inicial p. Por lo tanto, el autómata siguiente aceptará el mismo lenguaje:

Minimización de AF

Equivalencia de estados en AF

Sea el autómata finito determinista (å , Q, f, q₀, F). Decimos que dos estados p,qÎ Q son equivalentes (se representa por pEq) si para toda palabra xÎ å *, se verifica que f(p,x)Î FÛ f(q,x)Î F.

Nota: Si pEq entonces pE_nq, para todo n.

Propiedades de la equivalencia de estados

Dado AF=(å , Q, f, q₀, F), con p,qÎ Q

1. , pEq si " xÎ å * ® f(p,x)Î FÛ f(q,x)Î F

1. pE_kq (p y q son k-equivalentes) si: " xÎ å * | |x|<=k ® f(p,x)Î FÛ f(q,x)Î F
2. Ambas relaciones de equivalencia E y E_k inducen una partición de equivalencia sobre el autómata finito. Es decir: E induce P_E, y E_k induce P_k.
3. La primera partición que se establece es P₀, se hace con: p E₀q Û ( pÎ FÛ qÎ F). Nota: Entonces P₀={ (Q-F),F}
4. E_k,si pE_kq Þ pE_vq " v<k; si pEq Þ " k pE_kq.

LEMA1(propiedad de estados)

Si pE_k+1q Þ pE_kq y f(p,a)E_kf(q,a) " aÎ å

LEMA2

P_k=P_{k+1 Þ} P_k= P_E

LEMA3 (Se va a establecer cuando se estabiliza el valor de la partición)

Si |Q| = n >1 Þ pE_nq Û pE_n-2q

Es decir, n-2 es el grado de equivalencia menor al que habría que llegar para conseguir confirmar la equivalencia de dos estados en un autómata con n estados.

TEOREMA

Si |Q|=n>1 Þ $ j<=n-2 | P_j= P_j+1

Algoritmo para construir P_E

1. P₀={ { q_iÏ F} ,{ q_iÎ F} }

1. P_n+1={ pE_n+1q Û pE_nq y f(p,a)E_nf(q,a) " aÎ å }
2. P_n =P_n+1 =P_E

Ejemplo :

Para hallar las partes de equivalencia del autómata primero debemos partir de un autómata finito conexo. Para ello vamos a eliminar q₄, ya que no es posible acceder a él desde el estado inicial (q₁). Ahora vamos a establecer las partes de equivalencia:

® P₀={ Q-F, F} ={ { q_1} , { q₂, q_{3} }}

Ahora hacemos P₁, para ello sabemos que { q_1} va a seguir igual, es decir, va a ser equivalente con sigo mismo, puesto que accede a los mismo estados(finales o no finales).

Miramos { q₂, q_3} y comprobamos si acceden al mismo tipo de estado para las mismas entradas, es decir, sabiendo que q₂ E₀ q₃ vamos a ver si q₂ E₁ q₃:

f(q₂,a)=q_3Î F f(q₂,b)=q_1Ï F

f(q₃,a)=q_2Î F f(q₃,b)=q_1Ï F

luego q₂ E₁ q_3.

P₁={ { q_1} , { q₂, q_{3} }} = P₀= P_E

Algoritmo para hallar el autómata mínimo de uno dado

1. Calcular el autómata conexo

1. Construir Q/E del autómata conexo obtenido en el punto anterior.
2. Calcular A’=(å ,Q/E,f’,C₀,F’), donde:

a. C₀ es la clase donde se encuentra q₀ ;

b. F’={ c | c contiene al menos un estado de F(es decir, existe un qÎ F, tal que qÎ c)} ;

c. f’: Q/E x å ® Q/E, donde

f’(c_i, a)= c_j Û $ q_i Î c_i y $ q_j Î c_j | f(q_i,a)=q_j

Ejemplo:

Es un autómata conexo, pues todos sus estados son accesibles, vamos a hallar las partes de equivalencia:

P₀={ { s,t,u,v} ,{ p,q,r} } (={ Q-F,F} )

miramos la equivalencia de las clases de equivalencia establecidas en P₀.

f(p,a) = pÎ F; f(p,b)= qÎ F;

f(q,a)= rÎ F; f(q,b)=pÎ F;

f(r,a)= rÎ F; f(r,b)=rÎ F;

aqui vemos que { p,q,r} se conserva pues tienen iguales transiciones a estados finales a partir de las entradas.

f(s,a)=tÏ F; f(s,b)=pÎ F

f(t,a)=tÏ F; f(t,b)=uÏ F

f(u,a)=tÏ F; f(u,b)=vÏ F

f(v,a)=vÏ F; f(v,b)=uÏ F

ahora vemos que mientras t,u,v tienen iguales transiciones a estados no finales para las mismas entradas, siguen siendo equivalentes, mientras que s para b transita a un estado final, ya será equivalente a los tres estados anteriores:

P₁={ { p,q,r} ,{ s} ,{ t,u,v} }

Ahora hallamos P₂:

f(p,a) = pÎ F; f(p,b)= qÎ F;

f(q,a)= rÎ F; f(q,b)=pÎ F;

f(r,a)= rÎ F; f(r,b)=rÎ F;

f(t,a)=tÏ F; f(t,b)=uÏ F

f(u,a)=tÏ F; f(u,b)=vÏ F

f(v,a)=vÏ F; f(v,b)=uÏ F

P₂= { { p,q,r} ,{ s} ,{ t,u,v} } = P₁

luego P_E= { { p,q,r} ,{ s} ,{ t,u,v} }

 

 

 

El autómata mínimo nos va a quedar:

Si nos pidieran el lenguaje del autómata: L(A)=L(A’)={ b(a+b)*} , (donde A es el autómata inicial, y A’ es el autómata mínimo).

Autómatas Equivalentes

Suma directa de autómatas finitos deterministas

Sean los AFD A₁=(å , Q₁, f₁, q₀₁, F₁) y A₂=(å , Q₂, f₂, q₀₂, F₂), tales que Q₁ y Q₂ no tienen elementos comunes. Llamamos suma directa de A₁ y A₂ al autómata A=A₁+A₂=(å , Q₁UQ₂, f, q₀, F₁U F₂), dinde q₀ es uno cualquiera de los dos estados q₀₁ o q₀₂, y f se define así:

f(q,a)=f₁(q,a) si qÎ Q₁

f(q,a)=f₂(q,a) si qÎ Q₂

Equivalencia de autómatas

Sean los AFD A₁=(å , Q₁, f₁, q₀₁, F₁) y A₂=(å , Q₂, f₂, q₀₂, F₂). Decimos que dos estados pÎ Q₁ y qÎ Q₂ son equivalentes si f(p,x)Î F_1Û f(q,x)Î F₂, para todo xÎ å *.

Decimos que los dos autómatas son equivalentes si reconocen el mismo lenguaje. Es decir: si f(q₀₁,x)Î F_1Û f(q₀₂,x)Î F₂, para todo xÎ å *. Dicho de otro modo, decimos que dos autómatas son equivalentes si sus estados iniciales los son: q₀₁Eq₀₂.

Teorema.- Sean dos autómatas finitos deterministas A₁=(å , Q₁, f₁, q₀₁, F₁) y A₂=(å , Q₂, f₂, q₀₂, F₂), tales que Q₁ y Q₂ no tienen estados comunes y |Q₁|=n₁ y |Q₂|=n₂. Entonces, A₁ y A₂ son equivalentes si q₀₁ yq₀₂ son equivalentes en el autómata A=A₁+A₂, es decir, si ambos autómatas aceptan las mismas palabras de longitud menor que n₁+n₂-1. Además, en general, n₁+n₂-2 es el valor más pequeño que cumple siempre este teorema.

ALGORITMO PARA VER SI DOS AUTÓMATAS SON EQUIVALENTES

1. Calcular la suma directa de autómatas

1. Construir P_E del autómata suma obtenido
2. Comprobar que los estados iniciales son equivalentes, es decir, están en la misma clase de equivalencia. Cuando se da la condición: p₀₁, p₀₂ Î C₀ Þ A₁ y A₂ son equivalentes

Ejemplo:

El autómata suma me dará:

fÅ	a	b
® q1	q2	q1
*q2	q3	q1
*q3	q2	q1
q4	q1	q1
p1	p2	p1
*p2	p2	p1
p3	p2	p1

 

 

P₀={ { q₁, q₄, p₁, p_3} , { q₂, q₃, p_{2} }}

P₁={ { q₁, p₁, p_3} , { q_4} ,{ q₂, q₃, p_{2} }}

P₂={ { q₁, p₁, p_3} , { q_4} ,{ q₂, q₃, p_{2} }}

luego P₁= P₂ =P_E

Isomorfismo entre Autómatas

Se dice que A₁ es isomorfo a A₂, es decir, A_1» A₂ si $ i :Q_1® Q₂, (i : imagen). Por lo tanto :

1. i(p₀₁) = p₀₂ (la imagen del estado inicial de A₁ es el estado inicial de A₂.

1. Dados pÎ F₁, qÎ F₂ : i(p)Î F₂, y i(q)Î F₁.(es decir, la imagen de los estados finales de uno de los autómatas, es un estado final del otro autómata).
2. i(f₁(p₁,e)) = f₂(i(p₁),e) = f₂(i(p₂),e).La imagen de la transición es la transición de la imagen.

Por lo tanto A₁ y A₂ son iguales renombrando estados.

Entonces si dos autómatas son isomorfos van a ser equivalentes, es decir, los lenguajes que van a generar ambos autómatas van a ser el mismo : L(A₁) = L(A₂). Con esto comprobamos que la isomorfía implica la equivalencia.

Teorema : Si dos autómatas son equivalentes, entonces sus autómatas mínimos son isomorfos, es decir : A₁EA₂ Þ Â_1» Â₂ (siendo  _{i º} autómata mínimo de A_i).

 

Autómatas Finitos No Deterministas

Llamaremos "autómata finito no determinista" (AFND) a la séxtupla:

A = ( å , Q, f, q₀, F, T ), donde:

• å , Q,q₀, F significan lo mismo que en un autómata finito determinista.
• f es una aplicación de Q x å en el conjunto de las partes de Q
• T es una relación definida sobre pares de elementos de Q, donde p, q Î Q están en relación T( se representará por pTq, o (p,q)Î T) si existe una transición del estado p al estado q por medio de la palabra vacía l (l -transición).

Ejemplo: Sea el autómata finito no determinista:

({ a, b} , { p, q, r, s} , f, p, { p, s} , { (q,s), (r,r), (r,s), (s,r)} ), donde f se define asi:

f(p,a)={ q} f(p,b)=Æ

f(q,a)={ p,r,s} f(q,b)={ p,r}

f(r,a)=Æ f(r,b)={ p,s}

f(s,a)=Æ f(s,b)=Æ

 

Representación

En Diagrama: Con tantos nodos como estados.

Pueden sobrar o faltar arcos de un estado a otro

Si f(p,a)=Q₁, trazaremos una rama dirigida desde p hasta cada uno de los estados del conjunto de estados Q₁, con la etiqueta a.

Pueden existir arcos de un estado a otro por medio de l , en el caso de pTq, que trazaremos una rama desde p hasta q con la etiqueta l .

 

 

Ejemplo (continuación):

 

Tabla: Tendrá tantas filas como estados, y tantas columnas como elementos de å ,

más una columna adicional encabezada por la palabra vacía l , esta será la clumna reservada a las l -transiciones.

Ejemplo (continuación) :

	a	b	l
® p	{ q}
q	{ p,r,s}	{ p,r}	{ s}
r		{ p,s}	{ r,s}
*s			{ r}

 

Relación T

Sabemos que: (p,q) Î T*, donde T* = T⁰ È T¹ È T² È ....

Utilizaremos las matrices booleanas de representación T, para representar si un estado q es accesible desde un estado p mediante una l -transición.

Primero se representará la matriz booleana de representación de T, o, lo que es lo mismo, la matriz booleana que representa la posibilidad de transitar a otro estado a partir de una l -transición:

 

T	p	q	r	s
p	0	0	0	0
q	0	0	0	1
r	0	0	1	1
s	0	0	1	0

 

T*	p	q	r	s
p	0	0	0	0
q	0	0	1	1
r	0	0	1	1
s	0	0	1	1

 

Ahora se hace la clausura transitiva de la relación T, es decir, la relación T*, que no es más que calcular la accesibilidad de unos estados a otros mediante un número de l -transiciones mayor.

Lo que se ha hecho en esta clausura no es más que calcular aquellos estados q, que a partir de un estado p, es posible acceder mediante l -transiciones. Esto se puede ver tanto en el diagrama de estados, como en la matriz booleana de la relación T. Se puede observar que el estado r no accesible desde q mediante una l -transición, sin embargo si será accesible mediante dos l -transiciones. Este también será el caso del estado s y su acceso a sí mismo mediante l -transiciones.

 

Extensión de f a palabras

Ahora vamos a definir f’ como una nueva función de transición que, en lugar de actuar sobre letras del alfabeto de entrada, actúe sobre palabras (que incluyan la palabra vacía l ). Es decir: f’: Q x å * ® P(Q) (P(Q), partes de Q)

a) f’(q,l ) = { p | q T* p} , para todo qÎ Q

b) Sea x = a₁a₂...a_n , n > 0 . Entonces, f’(q,x) = { p | p es accesible desde q mediante la cadena de entrada l ⁱ⁰a_1l ⁱ¹a₂... a_nl ^in} para todo qÎ Q (la sucesión anterior es idéntica a x).

Ejemplo (en el autómata anterior):

f’(p,l ) = { p} f’(q,l ) = { q,r,s}

f’(r,l ) = { r,s} f’(s,l ) = { r,s}

f’(p,a) = { q,r,s} f’(p,b) = Æ