Gramáticas de sufijo

En la final del Mundial de Programación de la ACM (edición 2009), apareció un encantador problemita sobre gramáticas de sufijo, que es el problema K (suffix grammars) del problemario. 

Remontándonos a nuestras clases de lenguaje y castellano, un sufijo es una terminación de una palabra y la gramática es el conjunto de reglas que rigen la correctitud de las producción de secuencias de palabras.  En el contexto de la matemática y los lenguajes formales, estos dos conceptos tienen un significado parecido. En el problema en cuestión, una palabra es una secuencia (o cadena) de símbolos, los sufijos son las terminaciones de las palabras y la gramática va a ser el conjunto de reglas que nos van a permitir operar sobre los sufijos de una palabra y sustituirlo por otro sufijo.

Ejemplo:
Supóngase que tenemos una palabra inicial S="AA" que queremos transformar, mediante reglas gramaticales en una palabra T="BB", teniendo para ello las siguientes cuatro reglas:

Regla 1: "A" --> "B"
Regla 2: "AB" --> "BA"
Regla 3: "AA" --> "CC"
Regla 4: "CC" --> "BB"

Una manera de hacerlo sería, partiendo siempre de "AA", utilizar la regla 1 ("A" --> "B") y transformar "AA" en "AB". Luego aplicar la regla 2 para transformar el sufijo "AB" (o sea, toda la palabra) en "BA". Y por último, aplicando la regla 1 nuevamente, "BA" se transforma en "BB".

Otra manera (más directa) sería aplicar las reglas 3 y 4 sucesivamente, lo cual da la transformación en 2 pasos : "AA" --> "CC" --> "BB".

Se quiere desarrollar un programa en python que, dada una cadena inicial S, una cadena final T y un conjunto de reglas (la gramática), encuentre todas las transformaciones de S a T, mediante la aplicación de las reglas gramaticales, por supuesto.

continuará...