Se tiene un sistema formado por los siguientes símbolos: \(G, E, B\). Las expresiones de este sistema están formadas por combinaciones de las letras anteriores. Como en todo sistema, no toda combinación posible de símbolos es válida(por ejemplo, en matemáticas, \(2+2=5\) es una cadena bien formada, pero no es válida). Para obtener las cadenas válidas del sistema hacen falta unos axiomas, que son las proposiciones asumidas, y unas reglas, las cuales toman premisas y devuelven una conclusión. Si estas reglas se aplican sobre los axiomas o sobre cadenas válidas devolverán cadenas válidas. Nuestro axioma es la cadena \(GE\). Nuestras reglas son:
- Si se tiene una cadena cuya última letra es \(E\), se puede añadir una \(B\) al final.Por ejemplo, dado \(BE\), se puede obtener \(BEB\).
- Si se tiene una cadena de la forma \(Gx\), se tiene \(Gxx\). Aquí \(x\) representa una cadena cualquiera.Algunos ejemplos: dado \(GEB\), se puede obtener \(GEBEB\). Dado \(GBGE\), se puede obtener \(GBGEBGE\).
- Si en una cadena se tiene la secuencia \(EEE\), se puede obtener una nueva cadena sustituyendo \(EEE\) por \(B\). Por ejemplo, dado \(GEEEGB\), se puede obtener \(GBGB\).
- Si en una cadena se tiene la secuencia \(BB\), se puede obtener una nueva cadena eliminando \(BB\). Por ejemplo, dado \(GBBE\), se puede obtener \(GE\).
Partiendo de nuestro axioma, \(GE\), ¿se pueden obtener las siguientes cadenas aplicando las reglas (es decir, son válidas)?
- \(E\).
- \(GEBBE\).
- \(GBEEB\), con la condición de que no aparezcan más de 4 \(E\) seguidas en ningún paso.
- \(GB\).
Si la respuesta es afirmativa, hay que dar los pasos para obtenerla. En caso negativo, hay que explicar por qué no se puede.
Nota: las reglas solo se pueden usar una a la vez. Por ejemplo, si se tiene \(GBBEBB\) y se quiere obtener \(BE\) hay que hacerlos en dos pasos, aplicando la regla 4 dos veces: \(GBBEBB \to GEBB \to GE\).
