Equivalencia entre AFD y AFND. Hemos definido la equivalencia para los AFD. Extenderemos esta definición

para la clase de todos los autómatas finitos (AFD y AFND)de forma que un autómata M es equivalente a un autómata M’ si L(M) = L(M’).

 Ya que una función es un caso especial de relación (es decir, las funciones

son relaciones que poseen requerimientos adicionales), las funciones de los AFD se consideran como relaciones en los AFND. En consecuencia, todo AFD es un AFND. La colección d lenguajes aceptados por los AFND incluye a todos los lenguajes aceptados por los AFD. De esto resulta que los AFND solo aceptan lenguajes aceptados por los AFD. Por lo tanto, los AFND no son más potentes que los AFD con respecto a los lenguajes que aceptan. Para probar esto, necesitamos demostrar que todo lenguaje aceptado por un AFND también es aceptado por algún AFD.

 Sean M=(Q,,S,F,) un AFND. En el tema anterior presentamos una forma

de recorrer M, de la cual se obtenía la colección de todos los estados accesibles desde el estado inicial en cada una de las etapas de análisis de una cadena. Estas técnicas proporcionan la base para construir un AFD M’=(Q’,’,S’,F’,’) que acepte el mismo lenguaje que M. Esencialmente, lo que se pretende es hacer que cada estado Q’ se corresponda con un conjunto de estados Q. Cuando se analiza una cadena con M, esta se acepta cuando la colección finadle estados contiene al menos un estado de aceptación perteneciente a F. por tanto, haremos que F’ sea el conjunto de estados de Q’ que se correspondan con los conjuntos de estados (de Q) que contienen un estado de F. haremos corresponder a S’ con el conjunto {S}.’= y definiremos de forma que nos desplacemos de un conjunto de estados de M a otro, como se hace .

 Ahora demostraremos formalmente que todo lenguaje aceptado por un AFND

es también aceptado por un AFD, con lo que probaremos que los lenguajes AFND y los lenguajes AFD están formados por la misma colección de lenguajes.

 Teorema 1.- Sea M=(Q,,S,F,) un AFND. Entonces existe un AFD M’=

(Q’,’,S’,F’,’) que es equivalente a M.Demostración: Definamos M’=(Q’,’,S’,F’,’) como sigue: sea S’={S}, ’=,

Q’=2Q (que es la colección de todos los subconjuntos de Q) y F’ la colección de todos los conjuntos  de Q’ que contienen estados de F. Para cada conjunto (qi1,qi2,qin) de Q’ y cada  símbolo de entrada de , definiremos a  como:

 ({qi1, qi2, …,q1n},) ={p1,p2,…pk)({qi1,qi2,…,qin},) = {p1,p2,…,pk} Obsérvese que , definida de esta forma, es una función Q’x’ en Q’, puesto

que esta bien definida para todos los elementos de Q’x’.Para probar que L(M) = L(M’), debemos demostrar que para toda la cadena

w, (S’,w)={p1,p2,…,pj} si y solo si (S,w)={p1,p2,…,pj} con lo cual M’ acepta w si y

solo si M acepta w. Probaremos esto por inducción sobre la longitud de w. Si la longitud de w es 0 (es decir w=), entonces:

(S,w)= (S,) = {S} = (S’,w) Ahora supongamos que para toda cadena w de longitud menor o igual que m

se tiene que (S,w)=(S’,w). Supongamos que u es una cadena de longitud m+1. Entonces, existirá algún  , de forma que se obtiene que u=w, donde w es una cadena de longitud m. En este caso,  (S’w) = ((S’,w),). Ahora, por la hipótesis de inducción, dado que w tiene longitud m, (S’,w)= {p1,p2,…,pj} si y solo si (s,w)={p1,p2,…,pj}.Pero por la forma en la que hemos definido , tendremos que:

 ({p1,p2,…,pj},) = {r1,r2,…,rk}

si y solo si({p1,p2,…,pj},)= {r1,r2,…,rk}

 Por lo que (S’,w) = {r1,r2,…,rk} si y solo si (S,w) = {r1,r2,…,rk}. Es decir,

la igualdad se cumple para cadenas de longitud m+1 si se cumple para cadenas de longitud m. Entonces por lo anterior tenemos que (S’,w) es un estado de F’ si y solo si (S,w) contiene algún estado de F. Por tanto M’ acepta w si y solo si M acepta w.

Propiedades de los lenguajes aceptados por un autómata finito. Para un alfabeto se pueden construir los AFND (y los AFD) que acepten

palabras unitarias. Para ello se puede construir, incluso un AFND que acepte el lenguaje vacío .

Supongamos que M1= (Q1,1,S1,F1,1) y M2=(Q2,2,S2,F2,2) son AFND. Podemos unir M1 y M2 en un nuevo AFND que acepte L(M1)L(M2), añadiendo un nuevo estado inicial S y dos -transiciones, yna de s a si y otra de S a s2. La construccion formal de este nuevo AFND M=(Q,,S,F,) viene dado por =12, F=F1F2 y Q=Q1Q2{S}, donde S es el nuevo estado inicial y se define de forma que se incluyan todas las transiciones de 1,2 y las dos nuevas -transiciones de s a s1 y s2. Conviene considerar las relaciones de transición  1 y 2

como colecciones de ternas ordenadas de Q1xxQ1 y Q2xxQ2, donde (q,,p) significa que existe una transición de q a p mediante el carácter 8es decir, pi

(q,)). Usando esta notación se puede definir:=12{(s,,s1),(s,,s2)}

 Teorema.- El conjunto de lenguajes aceptados por un autómata finito sobre el

alfabeto contiene y los lenguajes unitarios {a} para todo a. Este conjunto es cerrado con respecto a la unión, concatenación y la cerradura de estrella.

Dada una expresión regular  r para construir un AFND (con -transiciones en todos los lados excepto para expresiones regulares triviales), podemos aplicar las técnicas precedentes a los términos de las expresiones regulares. Por tanto, todo lenguaje regular es aceptado por un autómata finito. Lo reciproco también es cierto, como veremos en el Lema de Arden. Es decir, todo lenguaje aceptado por

un autómata finito es también un lenguaje regular. Por lo tanto, el conjunto de los lenguajes regulares es el mismo que el conjunto de lenguajes aceptados por un autómata finito.

Consideremos el autómata finito M=(Q,,S,) y supongamos que s=q0 es el estado inicial. Para todo estado qi sea:

Ai={w* | (q1,w)F}Es decir, Ai es el conjunto de las cadenas sobre quehacer que M pase

desde qi hasta un estado de aceptación. Se dice que A i = . Si qiF, entonces se tiene que Ai.

 Lema de Arden: Una ecuación de la forma X=AXB, donde A, tiene una

solucion única X=A*B.Demostración: Obsérvese que A*B=(A+) B=A+BB=A(A*B)B. por tanto,

A*B esta contenida en toda solución. Supongamos que X=A*BC es una solución, donde CA*B=. Si resustituye la expresión anterior en la ecuación X=AXB, se obtiene

 A*BC= A(A*BC)B             = A+BACB             = A+BBAC             = (A+)BAC             = A*BACTeorema de Kleene: Un lenguaje es regular si y solo si es aceptado por un

autómata finito.

Autómatas finitos y expresiones regulares.Una expresión regular para un alfabeto se define como:

es una expresión regular Cada miembro de es una expresión regular Si p y q son expresiones regulares, entonces también lo es (p q) Si p y q son expresiones regulares, entonces también lo es (p q) Si p es regular, entonces también lo es p*

     Para cada expresión regular r de un alfabeto representa un lenguaje L(r). Además, si p y q son expresiones regulares, L(p q) = L(p) L(q), L(p q) = L(p) L(q) y L(p*) = L (p) *.      Las expresiones regulares también especifican lenguajes (al igual que diagramas tablas, autómatas y gramáticas) . Son una manera concisa de expresar lenguajes regulares (en una sola línea se puede describir un autómata finito completo). Teorema.- Dado un alfabeto (tiene que ser el mismo), los lenguajes regulares de son exactamente los lenguajes representados por las expresiones regulares de . Demostración.- Lo primero que hay que tener en cuenta es que un lenguaje representado por una expresión regular es regular (demostrado en los subapartados anteriores). Lo siguiente que haremos será representar con una expresión regular cualquier lenguaje aceptado por un autómata finito. Además, vamos a considerar válidos unos diagramas, que llamaremos generalizados, en los que los arcos van a estar etiquetados con expresiones regulares, en lugar de sólo símbolos. Para ello, vamos a ir reduciendo el diagrama hasta tener solo uno o dos estados:

a. Llamemos T al diagrama de transiciones original. Se hacen tantas copias de T como estados de aceptación haya. Cada Ti tendrá sólo un estado de aceptación distinto. La expresión regular resultante será la unión de cada una de las expresiones resultantes de cada Ti (T = T1 T2 .... Tn)

b. Considerando por separado cada Ti, y para ir reduciendo el diagrama estado por estado, se usan las operaciones que se definieron anteriormente:

c. Unión.- Si hay varios arcos que conectan en la misma dirección dos estados, estos se puede sustituir por uno etiquetado con la unión de las expresiones de esos arcos

d. Estrella de Kleene.- La expresión regular será la unión de las etiquetas de los arcos que salen e inciden en un mismo estado

e. Concatenación.- Hay dos casos: dado un estado, si solo tiene un arco incidente y otro saliente, la expresión resultante será la concatenación de las etiquetas del arco incidente y la del saliente; si en el estado tiene un arco solo incidente, arcos que salen e inciden en el mismo estado y un solo arco saliente, la expresión resultante será la concatenación de la etiqueta del arco incidente, la estrella de Kleene de la unión de las etiquetas de los arcos que iban del estado al mismo y la etiqueta del arco saliente por ese orden.

     Estas operaciones se van aplicando estado a estado, de manera que nos van quedando sucesivamente diagramas con n estados, n-1 estados, ..., 3 estados, y 2 ó 1 estado. En estos dos últimos casos:

a. Si el diagrama T queda con sólo un estado, que es inicial y de aceptación a la vez, la expresión resultante es la estrella de Kleene de la unión de las etiquetas de los arcos que salen e inciden en este mismo estado.

Que T quede con dos estados, uno inicial, y el otro de aceptación. Aquí se pueden tener alguno o todos de estos 4 arcos: (r)del inicial al inicial, (s) del inicial al de aceptación, (t) de aceptación a aceptación y (u) de aceptación al inicial. Si s no existe entonces la expresión regular es la cadena vacía, pues no se puede llegar a algún estado de aceptación. Si existe s pero no u entonces la expresión regular es (r* s t*). Si existe u entonces la expresión queda ((r* s t*) (u (r* s t*))*). Si r y t no existen son sustituidos por . Aquí r* representa la unión de las etiquetas de los arcos que salían y entraban en el mismo estado, como se dijo anteriormente.

Determinación de lenguajes regulares y no regulares. Es importante preguntarse su dado un lenguaje L, ¿L es regular?. Desde

luego, si L es finito, es regular, y de podrá construir un autómata finito o una expresión regular para ellos de forma sencilla. También si L es especificado ya sea por medio de un autómata finito o por una expresión regular, la respuesta es obvia. Por desgracia, hay relativamente pocos lenguajes que sean regulares y, en el caso de un lenguaje infinito, la búsqueda exhaustiva de una expresión regular o un autómata finito puede resultar inútil. En este caso, se necesita obtener algunas propiedades que compartan todos los lenguajes regulares infinitos y que no estén presentes en los lenguajes no regulares.

 

Supongamos que un lenguaje es regular y que, por tanto, es aceptado por un AFD M=(Q,,S,F,) donde Q tiene n estados. Si L(M) es infinito, podremos encontrar cadenas cuya longitud sea mayor que n. Supongamos que w=a1 a2 .. an+1 es una de las cadenas de longitud n+1 que pertenece a L(M). Si tuviéramos

q1 =  (S,a1)q2 = (q1,a2)

y así sucesivamente, obtendríamos los n+1 estados q1, q2, …, qn+1 . Puesto que Q contiene sólo n estados, los que qi no serán todos distintos. En consecuencia, oara algunos índices j y k, con 1 j < k n+1, se obtendrá que qj=qk. Por lo tanto, tendremos un ciclo en el camino que parte de S hasta un estado de aceptación.

 Puesto que j < k, se tiene que la “parte central” es decir a j +1 … ak, tiene al

menos longitud 1. Obsérvese además que la cadena w’=a1…aj ak+1 … an+1 debe pertenecer también a L(M) para todo m0. Es decir, se puede “bombear” cero o mas veces la parte central y seguir teniendo una cadena que sea aceptada por el autómata.

 Lema de bombeo.- Sea L un lenguaje regular infinito. Entonces hay una

constante n de forma que, si w es una cadena de L cuya longitud es mayor o igual que n, se tiene que w=uvx, siendo uvi xL para todo i 0, con |v| 1 y |uv| n.

 El lema de bombeo presenta una propiedad que debe tener todo lenguaje

regular y nos facilita una forma de determinar si un lenguaje no es regular. Para demostrar que un lenguaje no es regular, se mostrará que para cualquier valor n lo bastante grande, se tendrá al menos una cadena de longitud n o mayor que falle al ser “bombeada”.

Por ejemplo, considérese el lenguajeL={ai2 | i 1}

Toda la cadena de L debe tener una longitud que sea un cuadrado perfecto. Supongamos que L es regular y sea n la constante dada en el lema de bombeo. Obsérvese que an2 L y que, por el lema de bombeo, tenemos que an2 = uvx de forma que

1 |v| n  y  uvix L para todo i 1. Entonces se obtiene que: 

n2 = |uvx|< |uv2x| n2 + n< (n+1)2

 Es decir, la longitud de uv2x no puede pertenecer a L, es decir, L no puede

ser regular.

Autómatas bidireccionales

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 efectuar transiciones en función de una misma entrada leída varias veces. Veamos una formalización de esta noción de autómatas finitos. Un autómata bidireccional es una estructura de la forma

donde

La semántica del autómata es muy intuitiva: Si se está leyendo la i-ésima posición de una palabra de entrada, en la cual aparece el símbolo e, y se está en el estado q entonces,

si se pasa al estado p y a revisar la posición i-1 de la cadena de entrada,

si se pasa al estado p y a revisar la posición i+1 de la cadena de entrada.

Para llevar un recuento de las transiciones del autómata utilizaremos descripciones instantáneas (DI's). Una DI es una cadena

que indica que la palabra de entrada actual es , se está leyendo el

símbolo e y se está en el estado q: o bien de la forma

, que indica que se ha arribado al estado q y se ha concluido la lectura de la palabra de entrada.

Diremos que una DI se sigue de otra ,

, si es el resultado de aplicar la transición correspondiente a d0.

Formalmente,

La cerradura reflexivo-transitiva de la relación ``se sigue'' es la relación ``se deriva'',

denotada como .

Una palabra es reconocida por el autómata bidireccional si para algún estado

final se tiene . Es decir, una palabra es reconocida si para cuando se concluya su lectura se haya arribado a un estado final. El lenguaje reconocido por el autómata bidireccional es

Un lenguaje es regular-B si es reconocido por un autómata bidireccional.

Ejemplo

El autómata bidireccional que avanza a la derecha hasta que hayan aparecido dos 1's, y retrocede a la derecha hasta encontrar un 0, en cuyo caso reentra al estado

inicial,

tiene como transición a la siguiente:

El estado inicial es q0.

Si q1 se designa como estado final, entonces se reconocerá a palabras de la forma 0*(010*)*010*.

Ejemplo

Consideremos el semiautómata bidireccional de 6 estados sobre el alfabeto de dos símbolos A=[a,b]:

Una palabra que termina de leerse es . En la tabla (3.16) se ve la acción

de sobre .   

Table: Acción de sobre .

Una palabra con un prefijo de 4 a's hace que se salga por la izquierda de la

cadena de entrada. En efecto, consideremos . En la

tabla (3.17) se ve la acción de sobre .   

Table: Acción de sobre .

Una palabra que cicla es . En la tabla (3.18) se ve la acción de

sobre .   

Table: Acción de sobre .

Si se ve la entrada del autómata como inscrita en una cinta con casillas contiguas, en cada una de las cuales se inscribe un símbolo, entonces en una palabra de k símbolos habrá k+1

separadores de casillas. Si la palabra de entrada fuese , al escribir explícitamente a los separadores, podríamos re-escribir a como

En la figura (3.8) presentamos un diagrama de esta presentación.   

Figure 3.8: Cadena de entrada y

separadores en un AB.

La aplicación de la palabra de entrada en el autómata determina una sucesión de cruce Si en cada uno de los separadores si, de acuerdo con la construcción siguiente: 1.

Inicialmente hacemos y para cada i>0, . 2.

Posteriormente, si es la descripción instantánea actual,

es tal que y e está en la posición j, entonces

Con estas reglas, toda sucesión de cruce ha de comenzar con una pareja de la forma correspondiente a un movimiento a la derecha, y los movimientos correspondientes a dos parejas sucesivas en una misma sucesión de cruce habrán de alternarse. Por tanto, al cabo de la lectura de una palabra de entrada, en cada separador, la correspondiente sucesión de cruce ha de tener un número impar de elementos. Además, en el caso de que se haya aplicado una palabra que es efectivamente reconocida, ninguna sucesión de cruce puede tener dos apariciones de una misma pareja (en otro caso la ``computación'' se ciclaría).

Ejemplo Para la palabra de longitud 6, 101001, las 7 sucesiones de cruce en el semiautómata

bidireccional son las mostradas en la tabla 3.19.   

Table: Sucesiones de cruce para el autómata bidireccional .

Ejemplo Para la palabra de longitud 12, , las 13 sucesiones de cruce en el

semiautómata bidireccional son las mostradas en la tabla 3.20.   

Table: Sucesiones de cruce para el autómata bidireccional .

De manera general, diremos que una sucesión de cruce es una lista de parejas de la forma

tal que los movimientos en la sucesión se van alternando, y ninguna pareja se repite en la sucesión.

Por razones que se aclararán más adelante, diremos que una sucesión de cruce es derecha si comienza con un movimiento a la derecha y es de longitud impar. Simétricamente, diremos que es izquierda si comienza con un movimiento a la izquierda y es de longitud par. Si hay n estados en el autómata bidireccional, entonces ninguna sucesión de cruce puede

tener más de 2n elementos. Además, para cada hay sucesiones de cruce de

longitud 2j-1 que comiencen con el movimiento . Por tanto, con n estados, hay

posibles sucesiones de cruce derechas. El crecimiento de Cn es muy rápido como se ve en la tabla (3.21).

   Table 3.21: Crecimiento del número máximo de sucesiones de cruce.

En resumen, el conjunto de sucesiones de cruce para un autómata bidireccional siempre es finito. Por esto, tendremos que todo autómata bidireccional será equivalente a uno finito no-determinista. Los estados de éste último serán precisamente las sucesiones de cruce derechas posibles. En lo que resta de esta sección, veremos cómo convertir un autómata bidireccional a uno finito equivalente. Observemos en las tablas (3.19) y (3.20) que cualesquiera dos sucesiones de cruces contiguas ``concuerdan'' entre sí en el sentido de que sus construcciones son consistentes con el funcionamiento del correspondiente autómata bidireccional. Ahora bien, diremos que dos sucesiones de cruce S1, S2 concuerdan para un símbolo

si para alguna palabra , en la cual e aparezca en una posición, digamos i, se tiene que S1 aparece como subcadena de la sucesión de cruce Si-1, S2 aparece

como subcadena de Si y ambas cadenas forman la ``traza'' del funcionamiento del autómata bidireccional sobre la palabra . Diremos que S1 concuerda yendo a la derecha con S2 si la traza inicia con el primer elemento de S1 y el movimiento correspondiente es a la derecha. Similarmente, diremos que S2 concuerda yendo a la izquierda con S1 si la traza inicia con el primer elemento de S2 y el movimiento correspondiente es a la izquierda. Para poner esto en términos más precisos: D.1

La sucesión vacía concuerda yendo a la derecha consigo misma para cualquier símbolo e.

I.1 La sucesión vacía concuerda yendo a la izquierda consigo misma para cualquier símbolo e.

D.2 Si S1 concuerda yendo a la derecha con S2 para el símbolo e y

entonces la sucesión concuerda yendo a la derecha con S2 para el símbolo e.

En efecto, la pareja indica que se atraviesa al separador si-1 hacia la derecha para leer el símbolo e, y luego, por la acción del AB, se vuelve a atravesar si-1 pero ahora hacia la izquierda.

I.2 Si S2 concuerda yendo a la izquierda con S1 para el símbolo e y

entonces la sucesión concuerda yendo a la izquierda con S1 para el símbolo e. En efecto, estamos en una situación simétrica de la anterior.

D.3 Si S2 concuerda yendo a la izquierda con S1 para el símbolo e y

entonces concuerda yendo a la derecha con

para el símbolo e.

En efecto, la pareja indica que se atraviesa a si-1 hacia la derecha para leer el símbolo e, y luego, por la acción del AB, se atraviesa si hacia la derecha también. Posteriormente para mantener la concordancia es necesario que S2 concuerde yendo a la izquierda con S1.

I.3 Si S1 concuerda yendo a la derecha con S2 para el símbolo e y

entonces concuerda yendo a la izquierda con

para el símbolo e. En efecto, estamos en una situación simétrica de la anterior.

Se sigue inmediatamente lo siguiente: 1.

Si S1 concuerda yendo a la derecha con S2, entonces ambas sucesiones S1 y S2 son derechas.

2. Si S2 concuerda yendo a la izquierda con S1, entonces ambas sucesiones S1 y S2 son derechas.

3. Para cualquier palabra que se lea por completo en el autómata

bidireccional, si es su sucesión de sucesiones de cruce, entonces: (a) cada Si es una sucesión de cruce derecha, (b) cada Si-1 concuerda yendo a la derecha con Si, para el i-ésimo símbolo de la palabra .

Proposición 5.1 (Equivalencia de los autómatas bidireccionales con los no-deterministas)   Todo lenguaje regular-B es regular-N, y consecuentemente es también regular. Es decir, todo autómata bidireccional es equivalente a un autómata no-determinista, y consecuentemente a un autómata finito.

En efecto, sea un autómata bidireccional. Construyamos el autómata no-determinista siguiente:

estados:

, estado inicial:

, estados finales:

, transiciones:

Es fácil ver que ambos autómatas son equivalentes pues una ``computación reconocedora'', en el autómata no-determinista, corresponde a una lectura por columnas como las presentadas en las tablas 3.19 y 3.20, correspondientes a sendas ``computaciones reconocedoras'', en sus respectivos autómatas bidireccionales. El recíproco también vale.

El autómata descrito en la demostración anterior es muy extenso y seguramente ha de contener una gran cantidad de estados inaccesibles. Como una primera aproximación para reducir el tamaño del autómata equivalente podemos calcular sólo aquellas sucesiones de cruce que potencialmente pueden concordar, según lo permita la función de transición del autómata bidireccional. Describamos un procedimiento que dado un símbolo a produce sendas listas de parejas de sucesiones de cruce que concuerdan yendo por la derecha, abreviado ConcDer, y yendo por la izquierda, abreviado ConcIzq, respecto al símbolo a. Para cada una de las dos relaciones,

ConcDer y ConcIzq, utilizaremos un arreglo de palabras a revisar y otro de palabras ya revisadas. 1.

Inicialmente consideramos la sucesión de cruce vacía . La pareja se coloca en la lista de parejas a revisar, en tanto que la lista de parejas revisadas es vacía, para cada una de las dos relaciones de concordancia.

2. Por cada pareja de sucesiones que quede por revisar, (a)

se toma la primera pareja a revisar según ConcDer para pasarla a las ya revisadas tras el procesamiento que aquí describimos, (b)

para cada estado q sea el resultado de leer a en el estado q y

para cada pareja entre las revisadas o por revisar de la relación ConcIzq:

si entonces consideramos la pareja , para colocarla en la lista de las parejas a revisar según la relación ConcDer, si es que es la primera vez que aparece,

si entonces consideramos la pareja

, para colocarla en la lista de las parejas a revisar según la relación ConcDer, si es que es la primera vez que aparece,

(c) luego procedemos de manera dual, es decir, se toma la primera pareja

a revisar según ConcIzq para pasarla a las ya revisadas tras el procesamiento que aquí describimos, (d)

para cada estado q sea el resultado de leer a en el estado q y

para cada pareja entre las revisadas o por revisar de la relación ConcDer:

si entonces consideramos la pareja

, para colocarla en la lista de las parejas a revisar según la relación ConcIzq, si es que es la primera vez que aparece,

si entonces consideramos la pareja

, para colocarla en la lista de las parejas a revisar según la relación ConcIzq, si es que es la primera vez que aparece,

3. Las listas de parejas revisadas han de concordar.

El procedimiento descrito produce aún una gran cantidad de sucesiones de cruce, aunque efectivamente está descartando a muchísimas sucesiones irrelevantes.

Ejemplo

Volvamos al autómata . El algoritmo anterior produce 48 parejas de sucesiones de cruce derechas, de manera que la primera concuerda con la segunda yendo a la derecha, respecto al símbolo 0. En la tabla (3.22(a)) las enlistamos en su orden de aparición con el algoritmo descrito. Sin embargo, ahí aparecen también sucesiones que tienen elementos repetidos. En la tabla (3.22(b)) suprimimos esas sucesiones.

   Table 3.22: (a) Las 48 parejas de sucesiones de cruce derechas, de manera que la primera concuerda con la segunda yendo a la derecha, respecto al símbolo 0. (b)

Las 7 parejas de la tabla (a) sin sucesiones con elementos repetidos.

En la tabla (3.23) enlistamos las parejas de sucesiones de cruce derechas, de manera que la primera concuerda con la segunda yendo a la derecha, respecto al símbolo 1, también en el orden de aparición con el algoritmo descrito.

   Table 3.23: Las 10 parejas, de manera que la primera concuerda con la segunda

yendo a la derecha, respecto al símbolo 1.

Para el autómata , de 6 estados, este algoritmo da un número extremadamente grande de sucesiones relacionadas.

Como otra alternativa, en vez de generar todas las sucesiones de cruce plausibles, con cierta

noción de plausibilidad, partiendo de la sucesión de cruce primera , dada una sucesión de cruce actual calcularemos a todas aquellas que concuerdan con ella yendo a la derecha para cada uno de los símbolos en el alfabeto de entrada.

Para esto, definimos dos relaciones y de manera tal que para cualesquiera dos sucesiones de cruce S y T:

Diremos que una pareja es ``de zig-zag'', respecto al símbolo a si en la

transición del autómata bidireccional se tiene . Diremos también que un estado q

es un ``antecedente'' de si para algún símbolo b se tuviese que . De manera recursiva, tenemos: HD.1

. HD.2

. HD.3

. HI.1

es de zig-zag, respecto al símbolo a. HI.2

. Utilizaremos un arreglo de sucesiones de cruce a revisar y otro de sucesiones de cruce ya revisadas. 1.

Inicialmente se coloca la sucesión de cruce en la lista de sucesiones a revisar y la de revisadas es vacía.

2.

En tanto haya sucesiones por revisar, (a) se toma la primera sucesión S a revisar, para pasarla luego a las ya revisadas, (b) para cada símbolo a, i.

se calcula la lista de sucesiones T tales que , ii. se pone una transición, marcada con a de S a cada tal T, iii. la primera vez que aparezca una tal T, se la pone en la lista de sucesiones a revisar.

3. La lista de sucesiones revisadas define al autómata no-determinista equivalente.

Ejemplo

Para el autómata bidireccional , al aplicar el algoritmo anterior se distingue a las sucesiones de cruce

y con la enumeración de la primer columna, la transición del autómata no-determinista es

y sobre éste, al calcular el autómata determinista equivalente, obtenemos el autómata

donde la tabla del lado izquierdo representa una nueva enumeración ahora de los conjuntos de estados del autómata no-determinista, y la tabla de la derecha, la

transición del nuevo autómata determinista. Este es el equivalente a .

Ejemplo

Para el autómata bidireccional , al aplicar el algoritmo anterior se distingue a 177 sucesiones de cruce para formar el autómata no-determinista AND. Cuando a éste se le convierte en uno determinista, digamos AD, aparecen 63 estados. El estado 0 de AND

corresponde a la sucesión de cruce . El estado 0 de AD corresponde al conjunto de estados .

Vimos anteriormente que la palabra se lee por completo en el

autómata y arriba a su estado 3. Cuando aplicamos a AD se llega a su estado 49, el cual corresponde a la colección de estados de AND

entre los cuales está el estado 1 que corresponde a la sucesión de cruce

.

Producto de autómatas

Sean y dos autómatas finitos. Su semiautómata producto se define sobre el producto cartesiano como sigue: estados:

, estado inicial:

q01=(q01,q02), transiciones:

(se tiene un semiautómata porque aún no hay estados finales). Denotemos por

a este semiautómata. Es evidente que

Así pues, si definimos como conjunto de estados finales al conjunto

entonces una palabra será reconocida por el producto si y sólo si lo es

por alguno de los autómatas o , es decir, en este caso,

Ahora, si definimos como conjunto de estados finales al conjunto

entonces una palabra será reconocida por el producto si y sólo si lo es

por ambos autómatas o , es decir, en este caso,

Congruencias de autómatas

Sea un semiautómata. Una relación de equivalencia `` '' definida en el conjunto de estados Q se dice ser congruente con la función de transición si

  (9)

es decir para cada símbolo, los estados a los que transita el semiautómata desde sendos estados equivalentes son también equivalentes. Si `` '' es una

congruencia, entonces el cociente puede ser dotado de una estructura de semiautómata:

y éste se dice ser el semiautómata cociente respecto a la congruencia `` '',

denotado como . Se tiene pues que la proyección es un

homomorfismo de semiautómatas. Más aún, si es un autómata

finito y es una congruencia en el semiautómata , en el cociente

distinguimos como estados finales a las clases de la forma [q] tales que

, para obtener el autómata cociente . Aquí, la proyección es

un homomorfismo de autómatas. Consecuentemente, el cociente subsume al autómata .

Observación 2.3   Los autómatas y son equivalentes si y sólo si el conjunto de estados finales F es la unión de algunas clases de equivalencia respecto a `` ''. Para presentar unos primeros ejemplos de congruencias, consideremos homomorfismos de semiautómatas o autómatas. A lo largo de la presente sección, toda vez que hablemos de homomorfismos, supondremos que éstos son de hecho epimorfismos, es decir, como funciones, son suprayectivos. Sean pues

y dos semiautómatas y

un homomorfismo. Entonces su núcleo,

, es una relación de equivalencia que es de hecho

una congruencia. Por tanto, se puede definir el cociente , y éste es tal que cada clase de equivalencia corresponde biunívocamente a un elemento en la imagen de h. Así pues, lo expuesto aquí lo enunciamos como el

Teorema 2.1 (de homomorfismo de semiautómatas)   Si es un

epimorfismo de semiautómatas entonces el cociente es isomorfo a

. En símbolos, .

Para el caso de autómatas, si y son dos

autómatas y es un epimorfismo de autómatas, tal que

entonces es la unión de algunas clases de equivalencia

respecto a . Por tanto los autómatas y son isomorfos.

Teorema 2.2 (de homomorfismo de autómatas)   Si es un epimorfismo de autómatas tal que F1 es la unión de clases de equivalencia

respecto a , entonces el cociente es isomorfo a . En

símbolos, . Así pues, en cada pareja de semiautómatas o autómatas homomorfos que ya hemos visto, tendremos congruencias de semiautómatas o autómatas y correspondientes estructuras cocientes. Los ejemplos de homomorfismos de semiautómatas y de autómatas que ya hemos visto aquí, han de proporcionar ejemplos de congruencias y de autómatas cocientes.

TeoremaUn lenguaje en aceptado por un A.F.D. es aceptadopor un A.F.N.D.DemostraciónTrivial, ya que todo A.F.D. es un A.F.N.D.Ver apartado siguiente.

Paso de A.F.N.D. a A.F.D.

1. Se crea P(Q) y cada elemento de este nuevo conjuntoserá un estado del A.F.D. Si una componente de unelemento de P(Q) es un estado final, dicho elementoserá también un estado final.2. Añadir un nuevo estado w al que denominaremos estadomuerto.3. Las entradas serán las mismas.4. Si en la tabla de transición del A.F.N.D. un estado pasacon una entrada a varios estados, la combinación deéstos pertenece a P(Q), rellenando la casillacorrespondiente de la tabla de transición del A.F.D. condicho elemento de P(Q).5. Para rellenar las casillas de los elementos compuestosde P(Q) calculo todos los estados siguientes de cada unode los estados componentes de cada uno de dichoselementos de P(Q). El conjunto de todos estos estadossiguientes conforman otro elemento de P(Q),procediendo a su anotación en la tabla de transición del

A.F.D.6. Cualquier casilla que quede vacía la relleno con elestado w.7. Las casillas del estado w las relleno con el mismoestado w.Ejemplo: Obtener el A.F.D. asociado0 1A B, C*B A C*C CEjemplo: Obtener el A.F.D. asociadoG=({0, 1}, {S, U, V}, {SU0|V1, US1|1, VS1|0},S)

TeoremaUn lenguaje es aceptado por un -A.F.N.D. esaceptado por un A.F.N.D.DemostraciónTrivial, ya que todo A.F.N.D. es un -A.F.N.D.Ver algoritmo apartado siguiente.7. Algoritmo de paso de x-A.F.N.D. a A.F.N.D.Dado un lenguaje L aceptado por el -A.F.N.D.:A = (E, Q, f, q0, F)el A.F.N.D. que reconoce dicho lenguaje se construye dela siguiente manera:A’ = (E, Q, g, q0, F’)donde:0 ) ( } {0 ) ('00F q Cl si q FF q Cl si FFoyg(q, a) = f’(q, a)Teoría de Autómatas y Lenguajes Formales Tema 3. Autómatas FinitosProfesor: Jose Ignacio Gómez Espínola Pág. 138. Algoritmo alternativo de paso de x-A.F.N.D. aA.F.N.D.1. Calcular la clausura de todos los estados del -A.F.N.D.

que tienen transiciones nulas.2. Copiar la tabla de transición excepto la columnacorrespondiente a la cadena vacía.3. Para cada uno de los estados del -A.F.N.D. copiar ensu fila las filas de los estados de su clausura.4. Si en la clausura de algún estado hay algún estado finalincluir dicho estado dentro del conjunto de los estadosfinales.Ejemplo: A partir del -A.F.N.D. asociado al lenguaje L={0i1j2k |i,j,k0}, obtener el A.F.N.D. correspondiente.

9. TeoremaPara toda gramática tipo 3 existe un A.F.D. que aceptael lenguaje aceptado por la gramática.Demostración1. Generación de un x-A.F.N.D. a partir de una gramáticalineal por la derecha ver apartado 102. Generación de un x-A.F.N.D. a partir de una gramáticalineal por la izquierda ver apartado 11Finalmente, bastará con aplicar los algoritmos vistosanteriormente para pasar un -A.F.N.D. a A.F.N.D., y éstea A.F.D.Teoría de Autómatas y Lenguajes Formales Tema 3. Autómatas Finitos

AUTÓMATAS FINITOS NO DETERMINISTAS. MAQUINA CONCEPTUAL.

     La única diferencia con los anteriores está en que en la transición en un estado determinado puede haber, para un mismo símbolo, más de un arco o no haber ninguno.

     Decimos que un autómata finito no determinista acepta una cadena si es posible que su análisis deje a la máquina en un estado de aceptación. Decimos si es posible, pues si se toma el camino equivocado no se aceptaría una cadena que podría ser válida (una cadena del lenguaje aceptado por este autómata, designado por L(M).

     Formalmente el autómata finito no determinista consiste en una quíntupla (S, , , , F), donde

S es un conjunto finito de estados es el alfabeto de la máquina r es un subconjunto de S x x S (posibles transiciones de la máquina) i (un elemento de S) es el estado inicial F (un subconjunto de S) es la colección de estados de aceptación

     Un autómata de la forma (S, , , , F) acepta la cadena no vacía x1x2...xn si y solo si existe una serie de estados s0,s1,...sn tal que s0= y sn F y para cada entero j de 1 a n (sj-1,xj,sj) está en . Además, las tripletas (p,x,q) y (p,x,r), donde q y r son estados que pueden ser distintos, pueden estar en , diciéndose que al leer el símbolo x en el estado p se puede pasar al estado q o al r.      Para hacer un programa de un autómata no determinista se podría hacer probando todas las rutas una a una hasta que se terminasen o se aceptase la cadena, lo cual no es eficiente por la cantidad de memoria necesaria (crece exponencialmente con el número de estados).

     Para analizar una cadena en un autómata finito no determinista vamos a seguir todas las transiciones posibles en paralelo (atravesamos todas las rutas a la vez); la cadena se aceptará si alguna de las rutas acaba en un estado de aceptación. Nuestro estado en un momento dado ya no se hallará determinado por un estado del diagrama de transiciones, sino por la colección de los estados actuales de todas las rutas posibles; si K es la colección de estados actuales, al leer x del flujo de entrada obtendríamos un nuevo estado actual, representada por la colección de los estados a los que es posible llegar desde un estado K. Al pasar de conjuntos de estados a conjuntos de estados, se evitan los retrocesos (las rutas sucesivas distintas) además de superar el no determinismo del autómata. TEOREMA.- Para cada autómata finito no determinista, existe un autómata finito determinista que acepta exactamente el mismo lenguaje.

DEMOSTRACIÓN     Sea M = (S, , , , F), definimos entonces otro autómata M' determinista representado por el quíntuplo (S', , , ',F') donde:

S'=P(S) Conjunto de todos los subconjuntos de S (recordar que el conjunto potencia se encuentra incluido el conjunto vacío, que será el estado de captación global)

'={ } (mismo estado inicial) F' es la colección de subconjuntos de S (estados de S') que contienen,

por lo menos, un estado de F (cada uno de los estados de S' dentro de los cuales hay al menos un estado de aceptación de M)

es la función de S' x a S'; para cada símbolo del alfabeto y estado s' de S', (s',x) es el estado de S' compuesto por los estados de S a los que es posible llegar desde todos los estados s de s' siguiendo un arco con etiqueta x; al ser una función, M' es finito determinista.

M y M' aceptan exactamente las mismas cadenas, es decir, el mismo lenguaje; para demostrarlo hay que hacerlo sobre el enunciado: Para cada ruta en M del estado al estado sn , que recorre arcos w1, w2,..., wn existe una ruta en M' del estado ' al estado sn ' que recorre los arcos w1, w2,..., wn de modo que sn s'n y viceversa (para cada ruta en M' de ' recorriendo arcos w1, w2,..., wn y cada sn s'n, existe una ruta en M de a sn que recorre arcos w1, w2,..., wn ). (Se demuestra por inducción).

     Del anterior teorema se deduce que el no determinismo no permite que se acepte un conjunto mayor de cadenas. TEOREMA.- Para cualquier alfabeto , {L(M) es un autómata finito determinista con alfabeto } = { L(M) es un autómata finito no determinista con alfabeto }.

CONVERTIR UN DIAGRAMA NO DETERMINISTA EN UNO DETERMINISTA

 

     Cojamos el diagrama del siguiente autómata para el alfabeto ={a, b}. Como podemos ver, no es determinista pues desde el estado 1 salen dos arcos rotulados con b y del estado 2 salen dos arcos etiquetados con a.

 

     Para convertir el diagrama no determinista en uno que lo sea vamos ha realizar los siguientes pasos:

     S'=P(S) Conjunto de todos los subconjuntos de S (recordar que el conjunto potencia se encuentra incluido el conjunto vacío, que será el estado de captación global)      Como tenemos tres estados, el conjunto potencia P(S) = { , 1, 2, 3, 1-2, 1-3, 2-3, 1-2-3 }

     '= {} (mismo estado inicial)      En nuestro caso seguirá siendo el estado 1.

     F' es la colección de subconjuntos de S (estados de S') que contienen, por lo menos, un estado de F (cada uno de los estados de S' dentro de los cuales hay al menos un estado de aceptación de M).      En nuestro caso serán todos los subconjuntos que tengan el estado 3, ya que este es el único estado de aceptación del diagrama original; luego F'= { 3, 1-3, 2-3, 1-2-3 }

es la función de S' x a S'; Para cada símbolo del alfabeto y estado s' de S', (s',x) es el estado de S' compuesto por los estados de S a los que es posible llegar desde todos los estados s de s' siguiendo un arco con etiqueta x. Como es una función, M' es finito determinista.     En nuestro caso, En cada estado del conjunto potencia solo va a salir un arco por cada símbolo, siendo el destino, el estado de S' que tenga todos los estados a los que fuera en

el diagrama inicial: para ello:

+ vacío.- como dijimos, era el estado de captación global, por lo tanto se le dibujan tantos arcos que salen e inciden en el estado, como símbolos del alfabeto haya, con los cuales se rotulan. Además, en este estado, van a incidir todas aquellas transiciones que no existían para algún símbolo en algún estado original.

+ Estado 1.- Con la etiqueta a no hay transición en el original, por lo tanto el arco se dibuja hacia el estado vacío con la etiqueta b salen dos arcos, uno hacia el estado 2 y otro al estado 3, por lo tanto el arco se dibuja al estado 2-3

+ Estado 2.- Con la etiqueta b no hay transición en el original, por lo tanto el arco se dibuja hacia el estado vacío; con la etiqueta a salen dos arcos, uno hacia el estado 1 y otro al estado 3, por lo tanto el arco se dibuja al estado 1-3. + Estado 3.- Con ninguna de las dos etiquetas hay transición en el original, por lo tanto se dibujan sendos arcos hacia el estado vacío.

+ Estado 1-2.- Con la etiqueta a hay transición desde el estado 2 original al 1 y 3 original, por lo tanto el arco se dibuja hacia el estado 1-3; con la etiqueta b salen dos arcos desde el estado 1 original, uno hacia el estado 2 y otro al estado 3, por lo tanto el arco se dibuja al estado 2-3. + Estado 1-3.- Con la etiqueta a no hay transición desde ninguno de los dos estados originales, por lo tanto el arco se dibuja hacia el estado vacío; con la etiqueta b salen dos arcos desde el estado 1 original, uno hacia el estado 2 y otro al estado 3, por lo tanto el arco se dibuja al estado 2-3.

+ Estado 2-3.- Con la etiqueta a hay transición desde el estado 2 original al 1 y 3 original, por lo tanto el arco se dibuja hacia el estado 1-3; con la etiqueta b no sale ningún arco en ninguno de los dos estados originales, por lo tanto el arco se dibuja al estado vacío. + Estado 1-2-3.- Con la etiqueta a hay transición desde el estado 2 original al 1 y 3 original, por lo tanto el arco se dibuja hacia el estado 1-3; con la etiqueta b salen dos arcos desde el estado 1 original, uno hacia el estado 2 y otro al estado 3, por lo tanto el arco se dibuja al estado 2-3.

     Una vez que hemos terminado todos los pasos, podremos eliminar aquellos estados que sean superfluos al diagrama que acabamos de obtener.      En nuestro caso particular podemos eliminar los estados 2, 3, 1-2 y 1-2-3, quedando el definitivo autómata finito determinista.