Siguiente: Producto de autómatas Un nivel arriba: Autómatas finitos y expresiones Anterior: Supresión de transiciones vacías

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

$\begin{displaymath}\mbox{\it AB\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)\end{displaymath}$

donde

$\begin{eqnarray*}Q &:& \mbox{\rm es el conjunto de {\em estados},} \\ \mbox{\it... ...ubset Q &:& \mbox{\rm es el conjunto de estados {\em finales}.} \end{eqnarray*}$

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 $\mbox{\it tran\/}(q,e)=(p,\mbox{\it Izq\/})$ se pasa al estado p y a revisar la posición i-1 de la cadena de entrada,
si $\mbox{\it tran\/}(q,e)=(p,\mbox{\it Der\/})$ 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

$\begin{displaymath}\sigma_{\mbox{\scriptsize\it Izq}}qe\sigma_{\mbox{\scriptsize... ...nt\/}^*\times Q\times \mbox{\it Ent\/}\times \mbox{\it Ent\/}^*\end{displaymath}$

que indica que la palabra de entrada actual es $\sigma=\sigma_{\mbox{\scriptsize\it Izq}}e\sigma_{\mbox{\scriptsize\it Der}}$ , se está leyendo el símbolo e y se está en el estado q: $\sigma_{\mbox{\scriptsize\it Izq}}\begin{array}[t]{c} \underline{e} \\ \stackrel{\uparrow}{q} \end{array}\sigma_{\mbox{\scriptsize\it Der}},$ o bien de la forma $\sigma_{\mbox{\scriptsize\it Izq}}q\in\mbox{\it Ent\/}^*\times Q$ , que indica que se ha arribado al estado q y se ha concluido la lectura de la palabra de entrada.

Diremos que una DI $d_1=\sigma_{1,\mbox{\scriptsize\it Izq}}q_1e_1\sigma_{1,\mbox{\scriptsize\it Der}}$ se sigue de otra $d_0=\sigma_{0,\mbox{\scriptsize\it Izq}}q_0e_0\sigma_{0,\mbox{\scriptsize\it Der}}$ , $\mbox{\it AB\/}\vdash (d_0\rightarrow d_1)$ , si es el resultado de aplicar la transición correspondiente a d₀. Formalmente, $\mbox{\it AB\/}\vdash (d_0\rightarrow d_1)\Leftrightarrow$

$\begin{eqnarray*}&&\left\{\begin{array}{ll} \left[\begin{array}{lcl} (\sigma_{0... ...t tran\/}(q_0,e_0) &=& (q_1,\mbox{\it Izq\/}) \end{array}\right. \end{eqnarray*}$

La cerradura reflexivo-transitiva de la relación ``se sigue'' es la relación ``se deriva'', denotada como $\mbox{\it AB\/}\vdash (d_0\stackrel{*}{\rightarrow} d_1)$ .

Una palabra $\sigma \in \mbox{\it Ent\/}^*$ es reconocida por el autómata bidireccional $\mbox{\it AB\/}$ si para algún estado final $p\in F$ se tiene $\mbox{\it AB\/}\vdash (q_0\sigma\stackrel{*}{\rightarrow} \sigma p)$ . 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 $\mbox{\it AB\/}$ es

$\begin{displaymath}L(\mbox{\it AB\/})={[\sigma\in\mbox{\it Ent\/}^*\vert\exists ... ...it AB\/}\vdash (q_0\sigma\stackrel{*}{\rightarrow} \sigma p)]}.\end{displaymath}$

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

Ejemplo

El autómata bidireccional $\mbox{\it SAB\/}_3$ 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:

$\begin{displaymath}\begin{array}{\vert\vert r\vert c\vert c\vert\vert}\hline \hl... ...t Der\/}) & (q_2,\mbox{\it Izq\/}) \\ \hline \hline \end{array}\end{displaymath}$

El estado inicial es q₀.

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

Ejemplo

Consideremos el semiautómata bidireccional $\mbox{\it SAB\/}_6$ de 6 estados sobre el alfabeto de dos símbolos A=[a,b]:

$\begin{displaymath}\begin{array}{\vert\vert c\vert\vert c\vert c\vert c\vert c\v... ...ox{\it Izq\/}) & ( q_1, \mbox{\it Der\/}) \\ \hline \end{array}\end{displaymath}$

Una palabra que termina de leerse es $\alpha_1 = \mbox{\it aabbbababbbb\/}$ . En la tabla (3.16) se ve la acción de $\mbox{\it SAB\/}_6$ sobre $\alpha _1$ .

**Table:** Acción de $\mbox{\it SAB\/}_6$ sobre $\alpha _1$ .
$\begin{table}\begin{displaymath}\begin{array}{lr} \mbox{\it DI\/}[ 1]: & q_{ 0} ... ... & \mbox{\it aabbbababbbb\/} q_{ 3} \\ \end{array}\end{displaymath} \end{table}$

Una palabra con un prefijo de 4 a's hace que se salga por la izquierda de la cadena de entrada. En efecto, consideremos $\alpha_2 = \mbox{\it aaaabbbbaaaa\/}$ . En la tabla (3.17) se ve la acción de $\mbox{\it SAB\/}_6$ sobre $\alpha _2$ .

**Table:** Acción de $\mbox{\it SAB\/}_6$ sobre $\alpha _2$ .
$\begin{table}\begin{displaymath}\begin{array}{lr} \mbox{\it DI\/}[ 1]: & q_{ 0} ... ...x{\it !\lq Salida por la izquierda!\/} \\ \end{array}\end{displaymath} \end{table}$

Una palabra que cicla es $\alpha_3 = \mbox{\it aabbabaabbbb\/}$ . En la tabla (3.18) se ve la acción de $\mbox{\it SAB\/}_6$ sobre $\alpha _3$ .

**Table:** Acción de $\mbox{\it SAB\/}_6$ sobre $\alpha _3$ .
$\begin{table}\begin{displaymath}\begin{array}{lr} \mbox{\it DI\/}[ 1]: & q_{ 0} ... ...{\it DI\/}[11]\mbox{\it !\lq Ciclo!\/} \\ \end{array}\end{displaymath} \end{table}$

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 $\sigma=e_1\ldots e_{k}$ , al escribir explícitamente a los separadores, podríamos re-escribir a $\sigma$ como

$\begin{displaymath}\sigma=s_0e_1s_1\ldots s_{k-1}e_{k}s_{k}.\end{displaymath}$

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

**Figure 3.8:** Cadena de entrada y separadores en un AB.
$\begin{figure}\begin{center} \fbox{\begin{picture} (400,80)(0,0) \put(100,40){\l... ... \put(300,10){\framebox(0,0){$s_{k}$ }}\end{picture}}\end{center} \end{figure}$

La aplicación de la palabra de entrada $\sigma$ en el autómata determina una sucesión de cruce S_i en cada uno de los separadores s_i, de acuerdo con la construcción siguiente:

1.

Inicialmente hacemos $S_0=[(q_0,\mbox{\it Der\/})]$ y para cada i>0, $S_i=\mbox{\it nil\/}$ .

2.

Posteriormente, si $d=\sigma_{\mbox{\scriptsize\it Izq}}qe\sigma_{\mbox{\scriptsize\it Der}}$ es la descripción instantánea actual, $d'=\sigma_{\mbox{\scriptsize\it Izq}}'q'e'\sigma_{\mbox{\scriptsize\it Der}}'$ es tal que $\mbox{\it AB\/}\vdash (d\rightarrow d')$ y e está en la posición j, entonces

$\begin{eqnarray*}\mbox{\it tran\/}(q,e)=(q',\mbox{\it Izq\/}) &\Rightarrow& S_{j... ... &\Rightarrow& S_{j}\ \ \ =S_{j}\ \ \ *[(q',\mbox{\it Der\/})], \end{eqnarray*}$

Con estas reglas, toda sucesión de cruce ha de comenzar con una pareja de la forma $(q',\mbox{\it Der\/})$ 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 $\mbox{\it SAB\/}_3$ son las mostradas en la tabla 3.19.

**Table:** Sucesiones de cruce para el autómata bidireccional $\mbox{\it SAB\/}_3$ .
$\begin{table}{\small \begin{displaymath}\begin{array}{\vert\vert r\vert r\vert r... ...recha son un recuento secuencial de la computaci\'on. \end{center}}\end{table}$

Ejemplo

Para la palabra de longitud 12, $\mbox{\it aabbbababbbb\/}$ , las 13 sucesiones de cruce en el semiautómata bidireccional $\mbox{\it SAB\/}_6$ son las mostradas en la tabla 3.20.

**Table:** Sucesiones de cruce para el autómata bidireccional $\mbox{\it SAB\/}_6$ .
$\begin{table}{\small \begin{displaymath}\begin{array}{r} \begin{array}{\vert\ver... ...er\/}):19 \\ \hline \hline \end{array}\end{array}\end{displaymath}}\end{table}$

De manera general, diremos que una sucesión de cruce es una lista de parejas de la forma $(q,m)\in Q\times{[\mbox{\it Izq\/},\mbox{\it Der\/}]}$ 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 $j\leq n$ hay $c_{n,j}=\left(\frac{n!}{(n-j)!}\right)^2$ sucesiones de cruce de longitud 2j-1 que comiencen con el movimiento $\mbox{\it Der\/}$ . Por tanto, con n estados, hay

$\begin{displaymath}C_n=\sum_{j=1}^n c_{n,j}=\left(n!\right)^2\sum_{j=1}^n \frac{1}{\left((n-j)!\right)^2}\end{displaymath}$

posibles sucesiones de cruce derechas. El crecimiento de C_n 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.
$\begin{table}\begin{displaymath}\begin{array}{\vert\vert r\vert r\vert\vert r\ve... ...7324972436109660496552 \\ \hline \hline \end{array}\end{displaymath} \end{table}$

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 S₁, S₂ concuerdan para un símbolo $e\in\mbox{\it Ent\/}$ si para alguna palabra $\sigma =\sigma_1e\sigma_2$ , en la cual e aparezca en una posición, digamos i, se tiene que S₁ aparece como subcadena de la sucesión de cruce S_i-1, S₂ aparece como subcadena de S_i y ambas cadenas forman la ``traza'' del funcionamiento del autómata bidireccional sobre la palabra $\sigma$ . Diremos que S₁ concuerda yendo a la derecha con S₂ si la traza inicia con el primer elemento de S₁ y el movimiento correspondiente es a la derecha. Similarmente, diremos que S₂ concuerda yendo a la izquierda con S₁ si la traza inicia con el primer elemento de S₂ 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 S₁ concuerda yendo a la derecha con S₂ para el símbolo e y $\mbox{\it tran\/}(q_1,e)=(q_2,\mbox{\it Izq\/})$ entonces la sucesión $[(q_1,\mbox{\it Der\/}),(q_2,\mbox{\it Izq\/})]*S_1$ concuerda yendo a la derecha con S₂ para el símbolo e.
En efecto, la pareja $(q_1,\mbox{\it Der\/})$ indica que se atraviesa al separador s_i-1 hacia la derecha para leer el símbolo e, y luego, por la acción del AB, se vuelve a atravesar s_i-1 pero ahora hacia la izquierda.
I.2: Si S₂ concuerda yendo a la izquierda con S₁ para el símbolo e y $\mbox{\it tran\/}(p_1,e)=(p_2,\mbox{\it Der\/})$ entonces la sucesión $[(p_1,\mbox{\it Izq\/}),(p_2,\mbox{\it Der\/})]*S_2$ concuerda yendo a la izquierda con S₁ para el símbolo e.
En efecto, estamos en una situación simétrica de la anterior.
D.3: Si S₂ concuerda yendo a la izquierda con S₁ para el símbolo e y $\mbox{\it tran\/}(q_1,e)=(p_1,\mbox{\it Der\/})$ entonces $[(q_1,\mbox{\it Der\/})]*S_1$ concuerda yendo a la derecha con $[(p_1,\mbox{\it Der\/})]*S_2$ para el símbolo e.
En efecto, la pareja $(q_1,\mbox{\it Der\/})$ indica que se atraviesa a s_i-1 hacia la derecha para leer el símbolo e, y luego, por la acción del AB, se atraviesa s_i hacia la derecha también. Posteriormente para mantener la concordancia es necesario que S₂ concuerde yendo a la izquierda con S₁.
I.3: Si S₁ concuerda yendo a la derecha con S₂ para el símbolo e y $\mbox{\it tran\/}(q_1,e)=(p_1,\mbox{\it Izq\/})$ entonces $[(q_1,\mbox{\it Izq\/})]*S_2$ concuerda yendo a la izquierda con $[(p_1,\mbox{\it Izq\/})]*S_1$ para el símbolo e.
En efecto, estamos en una situación simétrica de la anterior.

Se sigue inmediatamente lo siguiente:

1.

Si S₁ concuerda yendo a la derecha con S₂, entonces ambas sucesiones S₁ y S₂ son derechas.

2.

Si S₂ concuerda yendo a la izquierda con S₁, entonces ambas sucesiones S₁ y S₂ son derechas.

3.

Para cualquier palabra $\sigma$ que se lea por completo en el autómata bidireccional, si $\left(S_i\right)_i$ es su sucesión de sucesiones de cruce, entonces:

(a): cada S_i es una sucesión de cruce derecha,
(b): cada S_i-1 concuerda yendo a la derecha con S_i, para el i-ésimo símbolo de la palabra $\sigma$ .

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 $\mbox{\it AB\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0,F)$ un autómata bidireccional. Construyamos el autómata no-determinista siguiente:

estados:
$Q_1={[\mbox{\rm sucesiones de cruce derechas}]}$ ,
estado inicial:
$q_{01}=[(q_0,\mbox{\it Der\/})]$ ,
estados finales:
$F_1={[[(q,\mbox{\it Der\/})]\vert q\in F]}$ ,
transiciones:
$(S_1\ e\ S_2)\in\mbox{\it tran\/}_1 \Leftrightarrow S_1 \mbox{\rm concuerda yendo a la derecha con }S_2\mbox{\rm para el s\'\i mbolo }e$

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 $\lambda$ . La pareja $(\lambda,\lambda)$ 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 $(\mbox{\it SDer\/}_1,\mbox{\it SDer\/}_2)$ a revisar según ConcDer para pasarla a las ya revisadas tras el procesamiento que aquí describimos,

(b)

para cada estado q sea $(p,\mbox{\it mov\/})$ el resultado de leer a en el estado q y para cada pareja $(\mbox{\it SIzq\/}_1,\mbox{\it SIzq\/}_2)$ entre las revisadas o por revisar de la relación ConcIzq:

si $\mbox{\it mov\/}=\mbox{\it Izq\/}$ entonces consideramos la pareja $({[[q,\mbox{\it Der\/}],[p,\mbox{\it Izq\/}]]}*\mbox{\it SDer\/}_1,\mbox{\it SDer\/}_2)$ , 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 $\mbox{\it mov\/}=\mbox{\it Der\/}$ entonces consideramos la pareja $({[[q,\mbox{\it Der\/}]]}*\mbox{\it SIzq\/}_1,{[[p,\mbox{\it Der\/}]]}*\mbox{\it SIzq\/}_2)$ , 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 $(\mbox{\it SIzq\/}_1,\mbox{\it SIzq\/}_2)$ a revisar según ConcIzq para pasarla a las ya revisadas tras el procesamiento que aquí describimos,

(d)

para cada estado q sea $(p,\mbox{\it mov\/})$ el resultado de leer a en el estado q y para cada pareja $(\mbox{\it SDer\/}_1,\mbox{\it SDer\/}_2)$ entre las revisadas o por revisar de la relación ConcDer:

si $\mbox{\it mov\/}=\mbox{\it Der\/}$ entonces consideramos la pareja $(\mbox{\it SIzq\/}_1,{[[q,\mbox{\it Izq\/}],[p,\mbox{\it Der\/}]]}*\mbox{\it SIzq\/}_2)$ , 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 $\mbox{\it mov\/}=\mbox{\it Izq\/}$ entonces consideramos la pareja $({[[p,\mbox{\it Izq\/}]]}*\mbox{\it SDer\/}_1,{[[q,\mbox{\it Izq\/}]]}*\mbox{\it SDer\/}_2)$ , 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 $\mbox{\it SAB\/}_3$ . 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.
$\begin{table}{\small \begin{displaymath}\begin{array}{cc} \begin{array}[b]{\vert... ... \hline \end{array} \\ (a) & (b) \end{array} \end{displaymath}}\end{table}$

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.
$\begin{table}{\small \begin{displaymath}\begin{array}{\vert\vert l\vert l\vert\v... ...mbox{\it Der\/})]} \\ \hline \hline \end{array}\end{displaymath}}\end{table}$

Para el autómata $\mbox{\it SAB\/}_6$ , 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 ${[(q_0,\mbox{\it Der\/})]}$ , 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 $\mbox{\it HaciaDer\/}_a$ y $\mbox{\it HaciaIzq\/}_a$ de manera tal que para cualesquiera dos sucesiones de cruce S y T:

$\begin{eqnarray*}S\mbox{\it HaciaDer\/}_a T &\ \Leftrightarrow\ &\mbox{\rm$S$\sp... ...e concuerda yendo a la izquierda con $S$\space respecto a $a$ } \end{eqnarray*}$

Diremos que una pareja ${[(q,\mbox{\it Izq\/}),(p,\mbox{\it Der\/})]}$ es ``de zig-zag'', respecto al símbolo a si en la transición del autómata bidireccional se tiene $\mbox{\it tran\/}(q,a)={[p,\mbox{\it Der\/}]}$ . Diremos también que un estado q es un ``antecedente'' de ${[p,\mbox{\it mov\/}]}$ si para algún símbolo b se tuviese que $\mbox{\it tran\/}(q,b)={[p,\mbox{\it mov\/}]}$ .

De manera recursiva, tenemos:

HD.1: ${[]}\mbox{\it HaciaDer\/}_a {[]}$ .
HD.2: ${[(q,\mbox{\it Der\/})]}*S\mbox{\it HaciaDer\/}_a {[(p,\mbox{\it Der\/})]}*T \ ... ...w\ (\mbox{\it tran\/}(q,a)= (p,\mbox{\it Der\/}))\&(S\mbox{\it HaciaIzq\/}_a T)$ .
HD.3: $[(q,\mbox{\it Der\/}),(p,\mbox{\it Izq\/})]*S\mbox{\it HaciaDer\/}_a T \ \Leftr... ...ow\ (\mbox{\it tran\/}(q,a)=(p,\mbox{\it Izq\/}))\&(S\mbox{\it HaciaDer\/}_a T)$ .
HI.1: ${[]}\mbox{\it HaciaIzq\/}_a T \ \Leftrightarrow\ T$ es de zig-zag, respecto al símbolo a.
HI.2: ${[(q,\mbox{\it Izq\/})]}*S\mbox{\it HaciaDer\/}_a {[(p,\mbox{\it Izq\/})]}*T \ ... ...mbox{\rm es antecedente de }(p,\mbox{\it Izq\/}))\&(S\mbox{\it HaciaIzq\/}_a T)$ .

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 ${[(q_0,\mbox{\it Der\/})]}$ 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 $S\mbox{\it HaciaDer\/}_a T$ ,
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 $\mbox{\it SAB\/}_3$ , al aplicar el algoritmo anterior se distingue a las sucesiones de cruce

$\begin{displaymath}\begin{array}{\vert\vert r\vert l\vert\vert} \hline \hline 0... ...it Izq\/}), (0,\mbox{\it Der\/})]} \\ \hline \hline \end{array}\end{displaymath}$

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

$\begin{displaymath}\begin{array}{\vert\vert r\vert l\vert l\vert\vert} \hline \h... ... \{2\} \\ \hline 5 & \{\} & \{\} \\ \hline \hline \end{array}\end{displaymath}$

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

$\begin{displaymath}\begin{array}{cc} \begin{array}[t]{\vert\vert r\vert l\vert l... ...\\ \hline 5 & 5 & 2 \\ \hline \hline \end{array} \end{array}\end{displaymath}$

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 $\mbox{\it SAB\/}_3$ .

Ejemplo

Para el autómata bidireccional $\mbox{\it SAB\/}_6$ , 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 $[(0,\mbox{\it Der\/})]$ . El estado 0 de AD corresponde al conjunto de estados $\{0\}$ .

Vimos anteriormente que la palabra $\sigma=aabbbababbbb$ se lee por completo en el autómata $\mbox{\it SAB\/}_6$ y arriba a su estado 3. Cuando aplicamos $\sigma$ a AD se llega a su estado 49, el cual corresponde a la colección de estados de AND

$\begin{displaymath}\begin{array}{c} \{ 1, 3, 23, 24, 25, 26, 27, 28, 29, 30, 34,... ...149,150,151,152,153, \\ 154,155,156,157,158,159\} \end{array}\end{displaymath}$

entre los cuales está el estado 1 que corresponde a la sucesión de cruce $[(3,\mbox{\it Der\/})]$ .

Siguiente: Producto de autómatas Un nivel arriba: Autómatas finitos y expresiones Anterior: Supresión de transiciones vacías

Guillermo Morales-Luna
2000-06-27