Gramaticas de sufijo, parte 2: la necesidad de arboles n-arios

Una forma de construir un algoritmo para buscar todas las formas posibles para transformar la cadena S a la cadena T sería esta: partiendo de la cadena inicial S verificamos cuales son las reglas aplicables.  Al aplicar dichas reglas a S obtenemos un conjunto de cadenas que "derivan" de ella.  A su vez, verificamos cuales son las reglas aplicables a cada una de las cadenas derivadas, las aplicamos y obtenemos otras cadenas , ...

Este proceso generaría una especie de árbol de búsqueda, donde un nodo representa una cadena, los arcos que salen de ese nodo representan la aplicación de determinada regla gramatical y estos arcos son aferentes a otros nodos, los cuales derivan del nodo padre mediante la aplicación de reglas.  Este árbol no sería del todo diferente al árbol de búsqueda que generan los programas de ajedrez cuando evalúan todas las posibles jugadas y respuestas del oponente en cada turno.  Para el ejemplo del post anterior, el árbol de búsqueda sería como este:
        
              AA
             /     \
            /       \
          AB     CC
           |         |
          BA     BB
           |
          BB

Se necesita etiquetar cada arco del árbol con el número de regla que produjo la transformación.  Observe que si hay muchas reglas, cada nodo podría tener muchos "hijos"- de ahí que necesitamos una estructura de datos parecida a un árbol n-ario, pero con los arcos etiquetados según la regla aplicada en cada transformación.  También hay que observar que en el proceso de verificar cuales reglas aplican a una cadena, pudiésemos obtener una cadena que ya ha sido producida y ya se encuentra en alguna parte del árbol.  Si agregamos nodos duplicados al árbol, el proceso de generar el árbol no terminaría nunca por la circularidad.  Por otro lado, cuando generamos un nodo igual a la cadena T, no se siguen generando más nodos hijos.  De hecho, aquellos nodos iguales a la cadena T son los únicos que pueden figurar repetidamente en el árbol y siempre se van a encontrar al final de alguna rama.  Si ninguna de las ramas del árbol termina en T, sabremos que no ha sido posible transformar S a T mediante la gramática dada.

Observese también que  una cadena (nodo) podría tener más de dos cadenas derivadas de ella, por lo cual no nos serviría un árbol binario como el que se describe en el capitulo 20 de "Pensar como programador".  Entonces, ¿como crear un árbol n-ario (n-ary tree) en python? Una busqueda por google me arrojo una página donde encontré esta definición de clase:


class Arbol:
    def __init__(self, nodo):
        self.nodo = nodo
        self.subarbol=[]
    def __str__(self):
        return str(self.nodo)
    def agregar_hijo(self,hijo):
        self.subarbol.append(hijo)

Para usar esta clase, creamos varias instancias de arboles, digamos a,b y c:

a=Arbol("arbol A")

b=Arbol("arbol B")

c=Arbol("arbol C")

luego, si por ejemplo queremos agregar los arboles b y c como hijos de a, haríamos lo siguiente:

a.agregar_hijo(b)

a.agregar_hijo(c)

Si queremos acceder a los hijos de a, navegariamos por la lista a.subarbol.  A su vez podemos agregarle nietos a a  (hijos de b o c) .  Este fue el punto de partida para desarrollar el programa que resuelve el problema de las gramaticas de sufijo.

continuara...