1 voto | Promedio: 9

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₁ 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₂ Þ Â₁ Â₂ (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) = Æ

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

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

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

f'(p,aa) = { p,r,s} f'(p,ab) = { p,r,s}

f'(q,aa) = { q,r,s} f'(r,ba) = { q,r,s}

 

Lenguaje aceptado por un AFND

El L(AFND) estará formado por el conjunto de cadenas que acceden a un estado final: L(AFND) = { x | x Î å * | f (q₀, x) = C_i | $ q_f Î C_i | q_f Î F }

La cadena vacía l , es aceptada por el AFND , cuando el estado final es un estado final: l Î L(AFND) si q₀ Î F ú q₀ T* q_f | q_f Î F (esto quiere decir que si l pertenece al lenguaje asociado al AFND entonces: O el estado inicial es también un estado final, o que el estado final es accesible mediante l -transiciones desde el estado inicial)

 

Autómata finito determinista equivalente a uno no determinista

Dado un autómata finito no determinista, siempre es posible construir otro finito determinista que acepta el mismo lenguaje que el primero. Puesto que el conjunto de lenguajes aceptados por los autómatas finitos no deterministas es idéntico al conjunto de los lenguajes finitos deterministas: L(AFD) = L (AFND)

Sea el autómata finito no determinista A = ( å , Q, f, q₀, F, T). Definiremos a partir de él el siguiente autómata finito determinista: B = ( å , Q', f', q'₀, F') donde:

• Q' = P(Q), el conjunto de las partes de Q, que incluye a Q y al conjunto vacío, Æ .
• q'₀ = f'(q₀, l ) (Estados a los que podemos ir desde q₀ mediante l -transiciones )
• F' = { c | cÎ Q' y existe un q Î c tal que q Î F} .
• f'(c,a) = { c' | c' = U_{qÎ c} f'(c,a) } . Es decir, como c es un subconjunto de Q, f'(c,a) es el subconjunto de Q formado por todos los estados a los que puede ir el autómata A, partiendo de un estado c, mediante la entrada a.

Ejemplo :

Sea el autómata finito no determinista definido por la tabla siguiente :

tendrá el diagrama siguiente :

Þ El autómata finito determinista equivalente será (por pasos) :

1º) p será el estado inicial

2º) (hallamos las partes de Q)

P(Q) = { Æ , { p} , { q} , { r} , { p, q} , { q, r} , { r, p} , { p, q, r} }

3º) Hago una tabla de transiciones, y pongo en la columna de estados aquellos que sean accesibles desde el estado inicial, no se ponen todas las partes de Q (P(Q)). Podría hacerse primero de esa forma, poniendo en los estados P(Q), pero después tendríamos que hallar el autómata conexo asociado.

 

	a	b
® { p}	{ p}	Æ
{ q}	{ q, r}	Æ
*{ r}	Æ	{ r}
*{ q,r}	{ q,r}	{ r}

Y este es el autómata finito determinista equivalente al no determinista.

Si nos pidieran minimizar el AFD obtenido:

Renombramos:

Hallamos el autómata equivalente hallando la partición de equivalencia correspondiente:

P₀={ { A,B,E} , { C,D} }

P₁={ { A,E} , { B} , { C} , { D} }

P₂={ { A} , { B} , { C} , { D} , { E} } = P_E luego el autómata ya es mínimo

 

Autómata finito no determinista equivalente a uno determinista

Un AFD es igual a un AFND sin l -transiciones.

 

Autómata Finito asociado a una Gramática Regular(Gramática tipo 3)

 

Notas

• El alfabeto no terminal de la Gramática y el conjunto de estados del AF van a "memorizar" el proceso.
• El conjunto de producciones de P "marchará en paralelo" con la función de transición f.
• En las gramáticas hemos hablado de depuración, lo cual podría considerarse como un símil a la minimización en un AF:

• Cuando tenemos un AFD vamos a tener una gramática depurada (excepción de GRLI)
• De un AFND Þ gramática ambigua
• De un AFND Þ AFD Þ gramática no ambigua
• Dada una gramática ambigua, a partie de ella podemos obtener un AFND de donde puedo obtener el AFD y a partir de aquí una gramática no ambigua.