Eventos representables

Cuando un evento puede ser descrito con algún tipo de notación, entonces decimos que dicho evento es representable. El teorema principal de ésta teoría dice:

Teorema 1   Un evento $E$ es representables si, y sólo si, este es regular.

La demostración de este teorema implica la demostración de que, la familia de las matricez cuadradas de dimensiones $n\times n$, forman una algebra de Kleene bajo las operaciones regulares. Esta demostración es extensa, por lo que se no se verá su totalidad en este documento, por lo que, sí el lector es interesado en examinarla, es posible encontrar dicha demostración en [JC71, cap. 3].
Conway escribió que, en cualquier máquina $M$ se define $E(\alpha,\beta)=\{w\mid \alpha_w=\beta\}$ como el conjunto de todas las palabras que lleven del estado $\alpha$ al estado $\beta$. También se define $E_l(\alpha,\beta)=\{w\mid \alpha_w=\beta,\ \mathrm{y}\ w\ \mathrm{tenga~ longitud}\ l\}$. Un evento de la matriz de transición esta definido por $M_{ij}=E_1(\alpha_i,\alpha_j)$ el conjunto de entradas que lleven del estado $\alpha_i$ al estado $\alpha_j$ en una sola transición. Se usará la misma letra para representar a una máquina $M$ y a la matriz de transición que describe su comportamiento y cuyas entradas son eventos. Para representar un evento regular definido por $LM^*N$, se debe definir $L$ y $N$ como sigue:
$L$ es un vector fila, que es el vector de entrada, el cual indica el estado inicial de la máquina, y cuyas entradas estan definidas como sigue parar el caso de una máquina binaria:

$$\begin{array}{ll} L_i= & \left\{ \begin{array}{ll} 1, & \mat... ...thrm{para~cualquier~otro~estado} \end{array}\right. \end{array}$$

El vector de salida esta definido por $N_j=o(\alpha_j)$. Las entradas de éste vector son salidas de $M$. En el caso en el que $M$ es una máquina binaria(con salidas 0 ó $1$), se pueden identificar las salidas 0 y $1$ como los eventos 0 y $1$ respectivamente.
De lo anterior se puede observar que $E_l= (M^l)_{ij}$, es el evento compuesto de las cadenas de longitud $l$ que llevan a $M$ de $\alpha_i$ a $\alpha_j$, de modo que $E(\alpha_i,\alpha_j)=(M^*)_{ij}$, es el evento de las cadenas de cualquier longitud que llevan a $M$ de $\alpha_i$ a $\alpha_j$, donde $M^*$ esta definida como $1+M+M^2+\ldots$, es decir, la suma infinita $\sum_{i=0}^{\infty}M^i$ de las potencias de la matriz. El $1$ representa a la matriz identidad de dimensiones $n\times n$. Para poder asegurar que un evento definido por $LM^*N$ es regular, debemos demostrar que las entradas de la matriz $M^*$ son eventos regulares, es decir, deben de ser funciones regulares de sus entradas.
Conway demostró en [JC71, cap. 3], que el sistema de las matrices de dimensiones $n\times n$ bajo las operaciones {$+,\cdot,*$} es cerrado, para ello Conway [JC71] definió una Algebra de Kleene Estandard (S-algebra, Standard Kleene Algebra) como un conjunto $S$ con tres operaciones { $\sum,\cdot,*$}(llamadas S-operaciones), definidas sobre $S$, y elementos particulares 0 y $1$, de tal manera que se cumplieran las siguientes propiedades:

S1 $\sum_t^{\emptyset}E_t=0$ ($\emptyset$ es el conjunto vacío)

S2 $\sum_s^S \sum_t^{T_s}E_t=\sum_t^U E_t\Bigg(U=\bigcup_s^S T_s\Bigg)$

S3 $E\cdot 1=1\cdot E$

S4 $E(FG)=(EF)G$

S5 $\sum_s^S E_s\cdot\sum_t^T F_t=\sum_{(s,t)}^{S\times T} E_s\cdot E_t$

S6 $E^*=\sum_n^\omega E_n(\omega=\{0,1,2,\ldots\})$

En $S5$, $T\times S$ indica el producto cartesiano de los conjuntos $S$ y $T$. La suma $\sum_t^T E_t$ esta definida para todo el conjunto de índices $t\in T$, y denota la suma $E_t$ de todos los eventos de longitud $t$ siempre que $t\in T$. $S6$ denota una definición de $E^*$ y es probable encontrarla continuamente. De lo anterior se tiene que $E_0+E_1=\sum_t^{(0,1)}E_t$.

Teorema 2   Si se define $E\leqslant F$ como $E+F=F$, entonces $\leqslant$ es una relación parcial de orden que es válida en cualquier S-algebra.

Demostración.Se pueden verificar los axiomas de transitividad, de tal manera que, $E\leqslant F\leqslant E$ es cierto, entonces, si sustituimos obtenemos que $E=E+F=F+E=F$, ya que tienen la propiedad de ser operaciones idempotentes, también se cumple que $X=\sum X=\sum (E_t+X)=\sum E_t+X$ siendo $X$ el menor evento que cumple con $X\geqslant E_t$.
    $\Box$

Teorema 3   En cualquier S-algebra $E^*G$ es el menor conjunto $F$ que satisface $F=G+EF$.

Demostración.Cualquier $F$ cumple con $F\geqslant EF$, por lo tanto $F\geqslant E^nF$ para cada $n\geqslant 0$, de donde tenemos que $F\geqslant E^nG$, ya que $F\geqslant G$, y sumando estas dos desigualdades para todo $n$, se obtiene que $F\geqslant E^*G$.    $\Box$

Para encontrar la estrella de una matriz $M$, cuyas entradas son eventos, utilizaremos la definición de la estrella de un evento $E^*= 1+EE^*$, esto es posible ya que el sistema de las matrices cuadradas es cerrado sobre las operaciones regulares. $1$ representa la matriz identidad.

Teorema 4   Si tenemos una matriz

$$M=\left(\begin{array}{cc} A & B\\ C & D \end{array}\right).$$

sobre una S-algebra, y la particionamos de forma que $A$ y $D$ sean matricez cuadradas, entonces:

$$M^*=\left(\begin{array}{cc} (A+D^*C)^* & A^*B(D+CA^*B)^*\\ D^*C(A+BD^*C)^*& (D+CA^*B)^* \end{array}\right)$$

Demostración.Definamos

$$M^*=\left(\begin{array}{cc} E & F\\ G & H \end{array}\right) ,$$

de tal modo que, desarrolando $M^*= 1+MM^*$, se obtiene:

$$M^*=\left(\begin{array}{rr} 1 & 0\\ 0 & 1 \end{array}\right) + \... ... \end{array}\right) \left(\begin{array}{rr} E & F\\ G & H \end{array}\right) ,$$

que puede ser representado por el siguiente sistema de ecuaciones:

1

$E=1+AE+BG$

2

$F=AF+BH$

3

$G=CE+DG$

4

$H=1+CF+DH$

Usando el teorema 3, se deduce el siguiente sistema:

(a) $E\geqslant(A+BD^*C)^*$

(b) $F\geqslant A^*B(D+CA^*B)^*$

(c) $G\geqslant D^*C(A+BD^*C)^*$

(d) $H\geqslant(D+CA^*B)^*$

Los valores de este último sistema satisfacen las ecuaciones del primer sistema, por lo que definen una matriz $N$, de tal manera que $N=1+NM$, cuando $N=M^*$.    $\Box$

Teorema 5   Las entradas en cualquier $M^*$, pueden ser expresadas como funciones regulares de las entradas de $M$.

Demostración.Para matrices de $1\times 1$, esto es muy sencillo. La manera de hacerlo para matrices de $2\times 2$, es igual a la forma en que se calcula la estrella de una matriz a la en el teorema 4, esto es, utilizando la definición $M^*= 1+MM^*$. Para una matriz de dimensiones $n\times n$ se puede seguir el siguiente procedimiento:

1. Particionaremos la matriz $M$ en cuatro submatricez, de tal manera que $D$ sea una matriz de dimensiones $(n-1)\times (n-1)$.
2. Ahora se le aplica el paso $1$ a la submatriz $D$ y así recursivamente hasta obtener una matriz de dimensiones $2\times 2$. El resultado de particionar a $M$ sera alguna matriz $D_i$ donde $i$ indica el nivel de profundidad de la matriz, es decir, el número de veces que se aplicó el paso 1.
   $$M=\left( \begin{array}{c\vert c} a_{11}&\cdots \\ \hline \vdots&... ...s 2}^{D_2} \end{array}\right)_{3\times 3}^{D_1} \end{array}\right)_{4\times 4}$$

3. Una vez que se tenga una matriz de $2\times 2$ se calcula su estrella de la misma manera que se calculo ateriormente, esto es $M^*= 1+MM^*$.
4. Por último, una vez obtenida $D^*_i$, se puede calcular $D^*_{i-1}$ de la misma forma, y así sucecivamente hasta calcular $M^*$

Es posible observar que las entradas resultantes de $M^*$ son funciones regulares de las entradas de $M$, con lo que se demuestra que $M^*$ es regular, y que cada una de sus entradas $M_{ij}$ es una expresión regular que define un lenguaje aceptado por un autómata cuyo estado inicial es aquel definido por $L_i$ y su estado final definido por $N_j$ autómata.    $\Box$

Hasta ahora se ha demostrado la mitad del teorema 1, y sabemos que cualquier evento representable cumple con que $E(1)$, para alguna máquina binaria, este evento es de la forma $LM^*N$ y además define una expresión regular. Para la segunda parte de la demostración se analiza el hecho de que un evento $E$, unicamente puede ser representado por una máquina si $E(1)=LM^*N$, donde:

• $L$ es un vector fila constante con un sólo 1.
• $M$ es una matriz lineal, con cada entrada ocurriendo sólo una vez en cada fila.
• $N$ es un vector columna constante.

Un evento es constante, si es 0 ó 1, lineal si es una suma de entradas, esta definición aplica también a matrices si, y sólo si, aplica a cada una de sus entradas.
Conway se libró de las dos restricciones anteriores al definir un tipo de máquina más general, llamado mecanismo lineal, el cual es un conjunto de objectos $\alpha_i$ llamados nodos, junto con tres funciones:

• Una función inicial, la cual asigna para cada $\alpha_i$ un evento $L_i$.
• Una función de transformación que asigna para cada par ($\alpha_i$ , $\alpha_j$) un evento lineal $M_{ij}$.
• Una función de salida, que asigna para cada $\alpha_i$ un evento constante $N_i$.

Este mecanismo lineal es un tipo especial de máquina, en la cual, en algún momento, un subconjunto de nodos definen el estado en el que se encuentra la máquina. Inicialmente sólo aquellos nodos $\alpha_i$ en los que $L_i=1$. Un nodo $\alpha_j$ se activa inmediatamente después de que la máquina recibe una entrada $a$ si, y sólo si, había un nodo $\alpha_i$ activo justo antes, y además $a\in M_{ij}$. Al igual que antes, el mecanismo sólo dará como salida $1$ cuando exista algún nodo $\alpha_j$ para el cual $N_j=1$.
El evento representado por el mecanismo lineal es $LM^*N$, el cual contiene todas las palabras que llevan a la máquina de su estado inicial, a estados en los que $o(\alpha)=1$.
De manera formal tenemos que los siguiente:

Teorema 6   E es representado por un mecanismo lineal si, y sólo si, E puede ser representado por una máquina.

Demostración.Podemos ver cualquier máquina como un mecanismo lineal definido por $(L,M,N)$, tomando los estados de la máquina como los nodos del mecanismo, de esta manera no se afecta el evento representado por la máquina, pero para cada mecanismo lineal $(L,M,N)$, podemos definir una máquina cuyos estados son un subconjunto de nodos $\alpha_i$, con $\alpha_a=\{\alpha_j\vert a\in M_{ij} \textrm{~para~alg\'un~} i \textrm{~para~el~cual~} \alpha_i\in\alpha\}$, una función de salida $o(\alpha)=1$, sólo si existen $\alpha_j\in \alpha$ para los cuales $L_j=1$, y con estado inicial definido por conjunto de nodos $\alpha_i$ en los que $L_i=1$. La máquina tendrá $2^n$ estados si $(L,M,N)$ tiene $n$ nodos, y representará el mismo evento que $(L,M,N)$.    $\Box$

Teorema 7   Un evento $E$ es representable si, y sólo si, puede ser expresado en la forma $E=L(C+D)^*N$, donde $L$ es un vector fila, $N$ es un vector columna, ambos constantes, $C$ es una matriz cuadrada constante, y $D$ es una matriz cuadrada lineal.

Demostración.Sabemos que $(C+D)^*=(C^*D)^*C^*$, entonces $L(C+D)^*N=L(C^*D)^*C^*N$, donde $(L,(C^*D)^*,C^*N)$ define un mecanismo lineal, dado que $(C^*D)^*$ es lineal, y $C^*N$ es constante.    $\Box$

Teorema 8   Cualquier evento regular es representable en la forma descrita por el teorema 7.

Demostración.Se pueden inducir los siguientes resultados de operaciones con eventos regulares, a partir de la demostración del teorema 4, y recordando la forma descrita por el teorema anterior, ésta es, $LM^*N$.

1. $0=0(0)^*0$
2. $1=1(1)^*1$
3. $$a= \left(\begin{array}{cc} 0 & 1 \end{array}\right) \left(% u... ...se packages: array \begin{array}{l} 1 \\ 0 \end{array}\right)$$
4. $$LM^*N+PQ^*R= \left(\begin{array}{cc} L & P \end{array}\right... ...use packages: array \begin{array}{l} N \\ R \end{array}\right)$$
5. $$LM^*N\cdot PQ^*R= \left(\begin{array}{cc} L & 0 \end{array}\... ...use packages: array \begin{array}{l} 0 \\ R \end{array}\right)$$
6. ( $$(LM^*N)^*= \left(\begin{array}{cc} 0 & 1 \end{array}\right) \... ...use packages: array \begin{array}{l} 0 \\ 1 \end{array}\right)$$

Lo anterior muestra que 0 , $1$ y las entradas (símbolos de entrada) pueden ser expresadas en la forma del teorema anterior y que si $E$ y $F$ son eventos que cumplen con ésta característica, entonces $E+F$ y $E\cdot F$ también lo harán.     $\Box$

Como un ejemplo tomemos el evento regular $E=(a^*b^*)^*$, para el cual $a^*$ y $b^*$ están son representados por los diagramas de la figura 4.

Figura 4: (a) $a^*$, (b) $b^*$.

Figura 5: Representación matricial de los eventos $a^*$ y $b^*$ en la forma $LM^*N$ descrita en el teorema 7.

De manera que usando la propiedad $5$, obtenemos

$$a^*b^*= \left( \begin{array}{cc\vert cc} 1 & 0 & 0 & 0 \end{array... ...ght]^* \left[ \begin{array}{c} 0 \\ 0 \\ \hline 1 \\ 0 \end{array}\right] ,$$

y usando la propiedad $6$ tenemos:

$$E= \left( \begin{array}{cccc\vert c} 0 & 0 & 0 & 0 & 1 \end{array... ... \left[ \begin{array}{c} 0 \\ 0 \\ 1 \\ 0\\ \hline 1 \end{array}\right] ,$$

Así podemos observar que $E$ es representado por el mecanismo de la figura 6(a), a partir de la cual podemos construir la máquina de la figura 6(b), omitiendo los estados inaccesibles. Como se puede observar el estado $\{\alpha,\beta, \gamma\}$ se repite en los tres nodos, proporciona la misma salida $(1)$ en todos los casos, y cada nodo es llevado por medio de $a$ y $b$ al mismo estado, por lo que estos estados son indistinguibles y la máquina puede ser reducida a la de la figura 7.

Figura 6: (a) Mecanismo, (b) Máquina; ambos representando $E=(a^*b^*)^*$.

Figura 7: Máquina reducida correspondiente a la figura 6(b).

Uno puede darse cuenta de que el mecanismo de la figura 6(a), no es un mecanismo lineal, sino un mecanismo-(constante+lineal), el cual está definido por una tupla de tres elementos $(L,C+D,N)$, en la forma descrita por el teorema 7. En éste tipo de mecanismo, la activación de un nodo $\alpha_i$ causa instantaneamente la activación del nodo $\alpha_j$ para el cual $C_{ij}=1$. Éste mecanismo-(constante+lineal) es equivalente a el mecanismo definido por $(LC^*,DC^*,N)$, el cual por medio del teorema 6, es equivalente a una máquina.
Hasta ahora hemos podido analizar como es que éste mecanismo lineal se asemeja mucho a la máquina de Turing mencionada en las primeras secciones, ya que nos permite emular el comportamientode cualquier máquina, y en el caso de un mecanismo lineal nos deja saber como se comportan dos o más de ellas si éstas son combinadas, probablemente éste principio, de hacer interactuar dos máquinas o mecanismos conociendo unicamente sus salidas se pueda aplicar en otros contextos con resultados interesantes.
Por último, para terminar con la demostración del teorema 1 se necesita probar el siguiente teorema.

Teorema 9   Existe un procedimiento efectivo para decidir si dos expresiones regulares $R$ y $S$ representan el mismo evento.

Demostración.Basta con construir dos máquinas $M$ y $N$ que representen a $R$ y $S$, entonces $R=S$ , sólo si las versiones mínimas de $M$ y $N$ son isomórficas, es decir, tienen el mismo comportamiento.     $\Box$

Nota: La versión mínima de una máquina $M$ es aquella máquina donde cada estado de $M$ es accesible, y cada par de estados distintos son distinguibles.