Vamos a encontrar que cualquier trabajo con un autómata celular lineal la posibilidad
de que sus vecindades se traslapen, para ello se revisa la teoria de la disiplina basada
en el tratamiento de secuencias que se traslapan, y es cuando surga la utilidad en la
teoria de autómata de manejar los diagramas de Bruijn, esto es explicado por Solomon
Golomb [5].
Los nodos en un diagrama de Bruijn son una secuencia de símbolos, similar a una
expresión regular, los cuales llevan una secuencia específica en la gráfica, las ligas
del diagrama describen como es que se traslapan estas secuencias, estos diferentes grados
de traslape, definen al diagrama, así las ligas pueden ser etiquetadas deacuerdo al sitio
desplazado como secuencia de otros caminos.
podemos citar el diagrama genérico de un autómata (2,1), dos estados tres
vecinos, el cual consta de cuatro nodos con ocho logas representando las tres vecindaes
llenas y se puede notar en el siguiente diagrama:
Figura 3.1: Diagrama de Bruijn para un Autómata Celular (2,1).
Ahora podemos particualrizar a cierta regla de un autómata, tomaremos un autómata (4,h), con sus respectivos subdiagramas, diferenciando los distintos estados con un color respectivo que le corresponde a su estado dentro de la evolución.
Figura 3.2: Diagrama de Bruijn para un autómata celular (4,h).