Caso $(4,1/2)$.

Tomemos el autómata reversible $(4,1/2)$ regla $E728D718$.

Tabla 6.11: Autómata $(4,1/2)$ regla $E728D718$

$\begin{array}{ccccc} &0&1&2&3 \\ \cline{2-5} \multicolumn{1}{c\vert}{0}& 0&2&... ...c\vert}{2}& 0&2&2&0 \\ \multicolumn{1}{c\vert}{3}& 3&1&2&3 \\ \end{array}$

Un ejemplo de la evolución de este autómta es el siguiente.

Figura 6.12: Autómata $(4,1/2)$ regla $E728D718$ y sus diagramas de Welch

Este autómata tiene índices de Welch $L=R=2$, tomemos los ancestros del estado $3$.

Tabla 6.12: Ancestros del estado 3

$\begin{array}{\vert c\vert} \hline 10 \\ 13 \\ 30 \\ 33 \\ 3 \\ \hline \end{array}$

Vemos en la Tabla 6.12 que los ancestros del estado $3$ tienen al conjunto $V=\left\{ 0,3 \right\}$ con $\vert V\vert=2$. Extendamos la secuencia a $32$ y veamos sus ancestros.

Tabla 6.13: Ancestros de la secuencia 32

$\begin{array}{\vert c\vert} \hline 101 \\ 132 \\ 301 \\ 332 \\ 32 \\ \hline \end{array}$

En la Tabla 6.13 se observa que todas las terminaciones derechas anteriores prosiguieron, con lo cual se conservó al conjunto $V=\left\{ 0,3 \right\}$ con $\vert V\vert=2$. Ya que la ruta es de longitud $2$ se cumple que $\vert V\vert \leq d-2=2$, donde los estados $1,2$ marcan las diferencias distintas de $V$ con respecto a $A_0$ y $A_2$ como indica el proceso. Veamos como se comportan los ancestros de $323$.

Tabla 6.14: Ancestros de la secuencia 323

$\begin{array}{\vert c\vert} \hline 1010 \\ 1013 \\ 3010 \\ 3013 \\ 323 \\ \hline \end{array}$

En la Tabla 6.14 ya no se pueden conservar todos los elementos de $V$ al extender la secuencia; por lo tanto existe una disminución en el valor de $\vert V\vert$ teniendo que $\vert V\vert =1$. De este modo ya se tiene un único nodo en común en los ancestros de la secuencia; los ancestros tienen así $L=2$ formas de empezar, $M=1$ variantes intermedias y $R=2$ formas de finalizar, haciendo un total de $LR=d=4$ ancestros.

Figura 6.13: Rutas del diagrama de de Bruijn de la forma $323$

En la Figura 6.13 el conjunto $A_0=\left\{ 1,3 \right\}$ es un nodo izquierdo de Welch y el conjunto $A_3=\left\{ 0,3 \right\}$ es un nodo derecho de Welch. Editando el diagrama de subconjuntos hagamos especial énfasis en la ruta $323$ empezando desde la clase completa y observando como se comporta en su recorrido.

Figura 6.14: Ruta $323$ en el diagrama de subconjuntos del autómata $(4,1/2)$ regla $E728D718$

Se observa en la Figura 6.14 que:

(a)

Al comenzar el recorrido existen $2$ formas distintas de terminar.

(b)

Dado que ya nos encontramos en el nivel de Welch $R=2$, las dos formas terminales anteriores se mantienen como variantes internas y $\vert V\vert=2$.

(c)

La ruta se extiende a una longitud $3$, si queremos que todas las variantes internas se conserven se deberá tener que $\vert V\vert=d-3=1$ cosa que no ocurre, o se debe perder al menos una alternativa en el recorrido lo cual si sucede, conservando solamente al estado $1$ como alternativa interna.

Las $d$ rutas finales en el diagrama de subconjuntos muestran $L=2$ nodos de de Bruijn izquierdos iniciales, $M=1$ variantes internas y $R=2$ nodos de de Bruijn derechos finales.