next up previous contents
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{displaymath}\begin{array}{rlcl}
\mbox{\rm I.} & \sigma i &\rightarrow& \...
...rm IV.} & \sigma aa\tau &\rightarrow& \sigma \tau
\end{array}\end{displaymath}

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.
\begin{figure}\begin{center}\begin{picture}
(360,150)(-180,-75)\put(-160, 70){mi...
...vector(0,-1){13}}
\put(-40,-75){etc}
\end{picture}\end{center}
\end{figure}

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$.

next up previous contents
Siguiente: KENNINGS: Poesía antigua islandesa Un nivel arriba: Reglas de transformación Anterior: Reglas de transformación
Guillermo Morales-Luna
2000-06-27