Diagrama de de Bruijn

Una ruta que se forme en el diagrama de de Bruijn indica la evolución de una cierta secuencia; así, tenemos que en un autómata reversible, cada secuencia debe tener tantas rutas distintas que la generen como nodos existan en el diagrama cumpliendo con la multiplicidad uniforme. Además, para una cierta longitud, estas rutas que forman la misma secuencia deben empezar de $L$ maneras distintas, llegar a un nodo en común y de ahí continuar de $R$ formas diferentes. Veamos ahora el diagrama de de Bruijn del autómata $(4,1/2)$ regla $1B2D1E2D$:

Figura 6.2: Diagrama de de Bruijn del autómata celular lineal reversible $(4,1/2)$ regla $1B2D1E2D$

En el caso de autómatas de con radio de vecindad $r=1/2$, cada nodo está formado exactamente por una cadena de longitud $1$, también en este caso existen tantos nodos como estados en el autómata y cada nodo está conectado con todos los demás. En adelante al número de nodos en el diagrama de de Bruijn lo denominaremos como $d$.