Siguiente: Acceso en un semiautómata Un nivel arriba: Autómatas finitos Anterior: Homomorfismos

Monoide de un semiautómata

Sea $\mbox{\it SAF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$ un semiautómata finito. Consideremos la relación `` $\equiv_{\mbox{\scriptsize\it SAF}}$'' en el diccionario $\mbox{\it Ent\/}^*$ definida como sigue,

$$\forall \sigma_1,\sigma_2\in\mbox{\it Ent\/}^*:\ \sigma_1\equ... ...{\it tran\/}^*(q,\sigma_1)=\mbox{\it tran\/}^*(q,\sigma_2)],$$ (6)

es decir, dos palabras están relacionadas si ambas ``actúan'' de igual manera en todo el conjunto de estados. `` $\equiv_{\mbox{\scriptsize\it SAF}}$'' es una relación de equivalencia que es además ``congruente con la concatenación'':

$$\sigma_1\equiv_{\mbox{\scriptsize\it SAF}}\sigma_2,\tau_1\equ... ...\sigma_1\tau_1\equiv_{\mbox{\scriptsize\it SAF}}\sigma_2\tau_2.$$

Por tanto el cociente $S_{\mbox{\scriptsize\it SAF}}=\left(\mbox{\it Ent\/}^*/\equiv_{\mbox{\scriptsize\it SAF}}\right)$ tiene una estructura de monoide, y se dice ser el monoide del semiautómata SAF. Cada elemento en $S_{\mbox{\scriptsize\it SAF}}$ determina una función $Q\rightarrow Q$. Si n es el número de estados en Q, entonces hay nⁿ funciones de Q en Q y, consecuentemente, la cardinalidad de $S_{\mbox{\scriptsize\it SAF}}$, es decir, el índice de la relación `` $\equiv_{\mbox{\scriptsize\it AF}}$'', no puede exceder nⁿ. De hecho, esta es una cota que, aunque muy grande, llega a alcanzarse. Como un mero ejemplo de esto, sea Q un conjunto de n estados y $q_0 \in Q$ un estado distinguido como inicial. Sea $\left(f_{\nu}\right)_{\nu=1}^{n^n}$ una enumeración de Q^Q, es decir , del conjunto de todas las funciones $Q\rightarrow Q$. Ahora, consideremos un alfabeto $E=\left(e_{\nu}\right)_{\nu=1}^{n^n}$ de nⁿ símbolos distintos y sea SAF el semiautómata sobre Q que a cada símbolo $e_{\nu}$ le asocia la función $f_{\nu}$. Es claro que el monoide determinado por SAF coincide con Q^Q, dotado de la composición de funciones como operación, y tiene consecuentemente nⁿ elementos.


Ejemplos. Sea $\mbox{\it Ent\/}=\{0,1\}$. 1. Para el semiautómata con tabla de transición

$$\begin{array}{\vert\vert r\vert cc\vert\vert}\hline\hline \... ... & q_0 & q_3 \\ q_3 & q_1 & q_2 \\ \hline\hline \end{array}$$ (7)

se tiene que `` $\equiv_{\mbox{\scriptsize\it AF}}$'' se resume como sigue:

$$\begin{array}{\vert\vert l\vert c\vert\vert}\hline\hline \m... ...{c} 0123\\ 3210 \end{array}\right) \\ \hline\hline \end{array}$$

aquí, por $\left(\begin{array}{cccc} 0&1&2&3 \\ i_0&i_1&i_2&i_3 \end{array}\right)$ denotamos a la función $q_j\mapsto q_{i_j}$. De la tabla anterior es posible calcular la clase de equivalencia de cualquier palabra $\sigma \in \mbox{\it Ent\/}^*$. Dada una palabra $\sigma$, cada vez que se encuentra en ella una de las partículas de la primera columna de la tabla en la ec. (3.3), sustituímos a esa partícula por la primera en dicha columna. Procedemos recursivamente en tanto esto sea posible. Por ejemplo, la clase de 1010 se calcula como sigue:

$$1010=\underline{10}\;\underline{10}\rightarrow 0\;\underline{... ...ghtarrow \mbox{\it nil\/}\;\mbox{\it nil\/} = \mbox{\it nil\/}$$

Tenemos pues que en nuestro ejemplo hay 4 clases de equivalencia: $[\mbox{\it nil\/}],[0],[1],[01]$. La tabla de multiplicación del monoide de este semiautómata es la siguiente:

$$\begin{array}{\vert\vert r\vert llll\vert\vert}\hline\hline ... ...1]} & {[0]} & {[\mbox{\it nil\/}]} \\ \hline\hline \end{array}$$

2. Para el semiautómata con tabla de transición

$$\begin{array}{\vert\vert r\vert cc\vert\vert}\hline\hline \... ... & q_3 & q_2 \\ q_3 & q_3 & q_3 \\ \hline\hline \end{array}$$

se tiene que `` $\equiv_{\mbox{\scriptsize\it AF}}$'' se resume como sigue:

$$\begin{array}{\vert\vert l\vert c\vert\vert}\hline\hline \m... ...{c} 0123\\ 3333 \end{array}\right) \\ \hline\hline \end{array}$$

En este ejemplo hay 5 clases de equivalencia: $[\mbox{\it nil\/}],[0],[1],[01],[10]$. La tabla de multiplicación del monoide de este semiautómata es la siguiente:

$$\begin{array}{\vert\vert r\vert lllll\vert\vert}\hline\hline ... ... {[10]} & {[10]} & {[10]} & {[10]} \\ \hline\hline \end{array}$$

Presentamos a continuación un procedimiento para calcular el monoide de un semiautómata dado. Para cada palabra $\sigma \in \mbox{\it Ent\/}^*$, sea $\mbox{\bf t}_{\sigma}\in Q^Q$ el vector con entradas en Q, indicado por índices en Q, tal que para todo $q\in Q$, $\left(\mbox{\bf t}_{\sigma}\right)_q=\mbox{\it tran\/}^*(q,\sigma)$. Se tiene la recurrencia,

$$\forall \sigma\in\mbox{\it Ent\/}^*,e\in\mbox{\it Ent\/},q\in... ..._q=\mbox{\it tran\/}(\left(\mbox{\bf t}_{\sigma}\right)_{q},e).$$

Utilizaremos un arreglo de palabras a revisar y otro de palabras ya revisadas.

1.

Inicialmente se coloca la palabra vacía en la lista de palabras a revisar y la de revisadas es vacía.

2.

Para cada palabra por revisar,

(a)

se toma la primera palabra $\sigma$ a revisar,

(b)

si el vector $\mbox{\bf t}_{\sigma}$ coincide con el vector correspondiente a una palabra ya revisada, se asocia $\sigma$ a esa palabra y se continúa este ciclo,

(c)

en otro caso, se incorpora $\sigma$ a las ya revisadas y sus palabras hijas, $\sigma e$, $e\in\mbox{\it Ent\/}$, se colocan al final de la lista de palabras a revisar.

3.

La lista de palabras revisadas ha de contener al final el monoide del semiautómata.

De manera más precisa, presentamos un seudocódigo en la figura 3.6.

  

Figure 3.6: Cálculo del monoide de un semiautómata.

Ejemplos 1. Para el ejemplo 1 anterior, el algoritmo 3.6 genera la tabla mostrada en la tabla (3.4).

  

Table 3.4: Cálculo del monoide del ejemplo 1.

Ahí vemos que el monoide posee 4 elementos y la tabla generada por el algoritmo posee $2\cdot 4=8$ renglones.


2. Para el ejemplo 2 anterior, el algoritmo (3.6) genera la tabla mostrada en la tabla (3.5).

  

Table 3.5: Cálculo del monoide del ejemplo 2.

3. Consideremos el semiautómata de 5 estados sobre el alfabeto $\mbox{\it Ent\/}=\{a,b,c\}$ siguiente:

$$\begin{array}{\vert\vert r\vert ccc\vert\vert}\hline\hline ... ... & q_2 \\ q_4 & q_3 & q_2 & q_2 \\ \hline\hline \end{array}$$

El algoritmo (3.6) genera la tabla mostrada en la tabla (3.6-a).

  

Table 3.6: Cálculo del monoide del ejemplo 3.

En este ejemplo hay 5 clases de equivalencia: $[\mbox{\it nil\/}],[a],[b],[c],[ab]$. La tabla de multiplicación del monoide de este semiautómata se muestra en la tabla (3.6-b).


4. Sea n>0 y sea A_n el semiautómata consistente de n estados $q_0,q_1,\ldots,q_{n-1}$, cuya tabla de transición es la siguiente:

$$\begin{array}{\vert\vert l\vert cc\vert\vert}\hline\hline \... ...n-1} \\ q_{n-1} & q_{n-1} & q_0 \\ \hline\hline \end{array}$$

En otras palabras, la acción del estímulo 0 puede identificarse con la transposición $(0\ 1)$ y la de 1 puede identificarse con el ciclo $(0\ 1\ \cdots\ n-2\ n-1)$. Es bien sabido que en el grupo S_n de permutaciones de n objetos se cumple lo siguiente:

• Toda permutación es un producto de ciclos. Por tanto, los ciclos generan a S_n.
• Todo ciclo es un producto de transposiciones, de hecho,
  
  $$\begin{eqnarray*}(i) &=& (i\ j)(j\ i) \\ (i_1\ i_2\ \cdots \ i_r) &=& (i_1\ i_r)(i_1\ i_{r-1})\cdots(i_1\ i_2) \end{eqnarray*}$$
  
  Por tanto, las transposiciones generan a S_n.
• Para cada transposición $(i\ j)$ se tiene $(i\ j)=(0\ i)(i\ j)(0\ i)$. Por tanto, las transposiciones de la forma $(0\ i),i<n$, generan a S_n.
• Para cada transposición $(0\ j)$ se tiene $(0\ j)=(0\ j-1)(j-1\ j)(0\ j-1)$. Por tanto, las transposiciones de la forma $(j-1\ j),j<n$, generan a S_n.
• Si $\pi$ es una permutación cualquiera, se tiene que $(\pi(0)\ \pi(1))=\pi(0\ 1)\pi^{-1}$. Así,, si $\gamma_n=(0\ 1\ \cdots\ n-2\ n-1)$ entonces $(j-1\ j)=\gamma_n^{j-1}(0\ 1)\gamma_n^{n-j+1}$. Por tanto, $(0\ 1)$ y $\gamma_n$ generan a S_n.

Así pues, el monoide generado por el semiautómata coincidirá con el grupo de permutaciones S_n, el cual posee n! elementos. Al aplicar el algoritmo 3.6 sobre un semiautómata de la forma A_n se generará una tabla con un orden de $2\cdot n!$ renglones. En particular, para n=4, las 24=4! permutaciones quedan generadas por las palabras mostradas en la tabla (3.7).

  

Table 3.7: S₄ como semigrupo de A₄.

Lema 2.2   Sea $\mbox{\it SAF\/}$ un semiautómata finito. Entonces su monoide $S_{\mbox{\scriptsize\it SAF}}$ puede ser dotado de una estructura de semiautómata, y si $\mbox{\it AF\/}=(\mbox{\it SAF\/},F)$ es un autómata cuyo semiatautómata adyacente es SAF, entonces puede distinguirse a algunas clases de equivalencia de manera que el autómata resultante queda subsumido por $\mbox{\it SAF\/}$.

En efecto, como la relación `` $\equiv_{\mbox{\scriptsize\it SAF}}$'' es congruente con la concatenación se tiene bien definida la transición

$$\begin{eqnarray*}\mbox{\it tran\/}_S:S_{\mbox{\scriptsize\it SAF}}\times \mbox{\... ...\sigma],e) &\mapsto& \mbox{\it tran\/}_S([\sigma],e)=[\sigma e] \end{eqnarray*}$$

Consideremos a una clase de equivalencia $[\sigma]$ como un estado final si es que la función $Q\rightarrow Q$ que determina esa clase contiene es tal que envía al estado inicial q₀ de AF en un estado final. Es decir, hagamos

$$F_S=\{[\sigma]\in S_{\mbox{\scriptsize\it AF}}\vert\mbox{\it tran\/}^*(q_0,\sigma)\in F\}.$$

Seguiremos denotando por $S_{\mbox{\scriptsize\it AF}}$ al autómata así construído. Es evidente que el autómata $S_{\mbox{\scriptsize\it AF}}$ queda, en efecto, subsumido por AF, qed.


Así, por ejemplo, si $\mbox{\it AF\/}$ es un autómata finito y $S_{\mbox{\scriptsize\it AF}}$ es su monoide, visto como autómata, entonces la aplicación

$$\begin{eqnarray*}h:S_{\mbox{\scriptsize\it AF}} &\rightarrow& \mbox{\it AF\/} \\... ...&\mapsto& h([\sigma])=T(\sigma)=\mbox{\it tran\/}^*(q_0,\sigma) \end{eqnarray*}$$

es, evidentemente, un homomorfismo. Consecuentemente, el autómata $S_{\mbox{\scriptsize\it AF}}$ queda subsumido por el autómata $\mbox{\it AF\/}$ del que es monoide.

Proposición 2.2   Si existe un homomorfismo $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ entonces

1.

existe un homomorfismo de monoides $h_m:S_{\mbox{\scriptsize\it AF}_1} \rightarrow S_{\mbox{\scriptsize\it AF}_1}$, y

2.

existe un homomorfismo de autómatas $h_a:S_{\mbox{\scriptsize\it AF}_1} \rightarrow S_{\mbox{\scriptsize\it AF}_1}$, y, de hecho, los homomorfismos h_m y h_a coinciden.

En efecto, supongamos que $h:\mbox{\it AF\/}_1\rightarrow \mbox{\it AF\/}_2$ es un homomorfismo. Definamos

$$\begin{eqnarray*}h_m:S_{\mbox{\scriptsize\it AF}_1} &\rightarrow& S_{\mbox{\scri... ...ox{\scriptsize\it AF}_1})=[\sigma]_{\mbox{\scriptsize\it AF}_2} \end{eqnarray*}$$

Se tiene,

• h_m está bien definida, pues,
  
  $$\begin{eqnarray*}{[\sigma_1]_{\mbox{\scriptsize\it AF}_1}=[\sigma_2]_{\mbox{\scr... ...{\scriptsize\it AF}_2}=[\sigma_2]_{\mbox{\scriptsize\it AF}_2}, \end{eqnarray*}$$
  
  
• h_m preserva la concatenación, pues
  
  $$\begin{array}{lllll} h_m([\sigma_1]_{\mbox{\scriptsize\it AF... ...)\cdot h_m([\sigma_2]_{\mbox{\scriptsize\it AF}_1}),\end{array}$$
  
  

• h_m preserva al estado inicial,
  
  $$h_m([\mbox{\it nil\/}]_{\mbox{\scriptsize\it AF}_1})=[\mbox{\it nil\/}]_{\mbox{\scriptsize\it AF}_2}.$$
  
  

Así pues h_m es un homomorfismo de monoides. Y se ve directamente que h_a=h_m es también un homomorfismo de autómatas. qed


Reiteremos, para concluir esta sección, una observación ya hecha anteriormente: para cada estado $q\in Q$ en la parte accesible de un semiautómata $\mbox{\it SAF\/}=(Q,\mbox{\it Ent\/},\mbox{\it tran\/},q_0)$ existe una palabra $\sigma_q$ tal que $T(\sigma_q)=q$. Por tanto, para cualesquiera dos estados p,q en la parte accesible de $\mbox{\it SAF\/}$, rige la implicación,

$$p\not =q\ \Rightarrow\ [\sigma_p]_{\mbox{\scriptsize\it SAF}}\not =[\sigma_q]_{\mbox{\scriptsize\it SAF}}.$$

Así pues el monoide de $\mbox{\it SAF\/}$ tiene al menos tantos elementos cuantos tiene la parte accesible de $\mbox{\it SAF\/}$.
Siguiente: Acceso en un semiautómata Un nivel arriba: Autómatas finitos Anterior: Homomorfismos