Gramaticas de sufijo, parte 3: implementación en python

Sin más preámbulos, coloco el código Python que, dado una cadena S que se requiere transformar a T mediante una gramática de sufijo (conjunto de NR reglas), hace una búsqueda exhaustiva de todas las posibles maneras de transformar S a T:

#Definir estructura de datos (clase) para el arbol de busqueda
class Arbol:
    def __init__(self, nodo):
        self.nodo = nodo
        self.subarbol=[]
    def __str__(self):
        return str(self.nodo)
    def agregar_hijo(self,regla,hijo):
        self.subarbol.append(tuple([regla,hijo]))
    def contiene_nodo(self,nodo):
        """contiene el arbol al argumento como nodo?"""
        if self.nodo==nodo:
            return True
        else:
            if self.subarbol!=[]:
                cn=False
                for i in self.subarbol:
                    cn=cn or i[1].contiene_nodo(nodo)
                return cn
            else:
                return False           
    def aplicar_reglas(self,arbol):
        #primero aplica todas las reglas al nodo raiz
        for i in range(0,len(reglas)):
            su0=reglas[i][0]
            su1=reglas[i][1]
            no=self.nodo
            if no.endswith(su0):
                nuevo = no[:no.rfind(su0)]+su1
                if nuevo==T or not(arbol.contiene_nodo(nuevo)):
                    self.agregar_hijo(i,Arbol(nuevo))
        #luego se ramifica recursivamente para cada subarbol
        #(si hay subarboles hijos)
        if self.subarbol!=[]:
            for i in self.subarbol:
                i[1].aplicar_reglas(arbol)
    def recorrer_arbol(self,ruta):
        """recorre todo el arbol retornando las rutas que terminan en T"""
        global rutas
        if self.nodo==T:
            rutas.append(ruta)
        else:
            for i in self.subarbol:
                i[1].recorrer_arbol(ruta+[(i[0],i[1].nodo)])

def imprimir_rutas():
    if rutas==[]:
        print "No es posible transformar",S,"en",T,"mediante esta gramatica."
    else:
        for i in range(0,len(rutas)):
            print "Transformacion",i+1,":"
            print S,"\t-->",
            for j in rutas[i]:
                print j[1],"\tRegla",j[0]+1,": (",
                print reglas[j[0]][0],"-->",reglas[j[0]][1],")"
                if not(j==rutas[i][-1]):
                    print "\t-->",
               
#PROGRAMA PRINCIPAL
#Lee S, T y las reglas del archivo
archivo=open("suffix.in","r")
s=archivo.readline().split(" ")
S=s[0]
T=s[1]
NR=int(s[2])
reglas=[]
for i in range(0,NR):
    s=archivo.readline().strip().split(" ")
    reglas+=[tuple(s)]
archivo.close()
#Genera el arbol de busqueda
ab=Arbol(S)
ab.aplicar_reglas(ab)
#recorre el arbol de busqueda para generar las rutas que
#culminan en T
rutas=[]
ab.recorrer_arbol([])
imprimir_rutas()

Este script requiere de un archivo en donde se coloca la cadena inicial S, la cadena final T y el número de reglas (NR) en la primera línea, separados por espacio.  Las siguientes NR líneas del archivo contienen las reglas gramaticales.  Para probar el script, tome las siguientes líneas y cree con ellas un archivo llamado "suffix.in" en el mismo directorio que "suffix.py" (el script de arriba):

AA CB 6
C B
AB BA
AA CC
CC BB
C A
A B

Con esta data de entrada en el archivo "suffix.in", el programa generaría la siguiente salida:

Transformacion 1 :
AA     --> CC     Regla 3 : ( AA --> CC )
       --> CB     Regla 1 : ( C --> B )
Transformacion 2 :
AA     --> CC     Regla 3 : ( AA --> CC )
       --> CA     Regla 5 : ( C --> A )
       --> CB     Regla 6 : ( A --> B )