Siguiente: KENNINGS: Poesía antigua islandesa Un nivel arriba: Reglas de transformación Anterior: Reglas de transformación

MAI : Modos Mecánico, Anti e Inteligente (Zen)

Este ejemplo aparece en el capítulo 1 del libro de Hofstadter ([15]). Consideremos las reglas siguientes:

$$\begin{array}{rlcl} \mbox{\rm I.} & \sigma i &\rightarrow& \... ...rm IV.} & \sigma aa\tau &\rightarrow& \sigma \tau \end{array}$$

Los caracteres griegos representan a palabras en el alfabeto $\mbox{\it MAI\/}=\{m,a,i\}$. La primera regla dice que a toda palabra que termina con i puede añadírsele una a, la segunda, que toda palabra que comience con m puede repetir su ``resto'', la tercera, que cualquier cadena de tres i-es consecutivas puede cambiarse por una a, y, finalmante, que cualesquiera dos a-es consecutivas pueden ser suprimidas. Como ejemplos de derivaciones están los mostrados en la figura (3).

  

Figure 3: Derivaciones en el sistema MAI.

Para cada palabra $\sigma$ sea $\mbox{\it MAI\/}(\sigma)$ el conjunto de palabras en el alfabeto MAI que pueden ser derivadas a partir de la palabra $\sigma$ mediante una sucesión finita de aplicaciones de las reglas de transformación. Naturalmente, surgen los problemas siguientes:

Problema de la palabra.

Dadas dos palabras $\sigma, \tau$ decidir si acaso $\tau\in \mbox{\it MAI\/}(\sigma)$, es decir, decidir si acaso una palabra es o no derivable desde alguna otra.

Problema de equivalencia.

Dadas dos palabras $\sigma, \tau$ decidir si acaso $\mbox{\it MAI\/}(\sigma) = \mbox{\it MAI\/}(\tau)$, es decir, decidir si acaso cualquier palabra es derivable desde una de las dos palabras si y sólo si es derivable desde la otra.

Problema de derivación óptima.

Dadas dos palabras $\sigma, \tau$ tales que $\tau\in \mbox{\it MAI\/}(\sigma)$, localizar la sucesión de transformaciones más corta que transforma a $\sigma$ en $\tau$.

Siguiente: KENNINGS: Poesía antigua islandesa Un nivel arriba: Reglas de transformación Anterior: Reglas de transformación