El diagrama de de Bruijn es una gráfica cuyos nodos (secuencias de símbolos de algún
alfabeto) son secuencias de un conjunto de estados y sus ligas describen las secuencias
que se traslapan revelando las posibles sucesiones. Dichas secuencias tienen la misma
longitud y son vecindades parciales.
Para un autómata (k,r) el número de nodos, en el diagrama, está dado por
y el número de ligas por
Ya que los nodos representan fracciones de vecindades saldrá una liga del nodo i al
nodo j si y sólo si la fracción de vecindad de el nodo i junto con la del nodo j forman
una vecindad completa. Cada fracción de vecindad para cada nodo está dada por 2r [5].
La matriz de conectividad que como sigue,
