Reglas de re-escritura1
Una regla de re-escritura (o de re-emplazo) es un par ordenado de palabras u, v que denotamos como u\to v\ . Decimos que esta es la regla que nos permite transformar u en v.
Ejemplo 1 La regla de re-escritura ab\to bba es la regla que nos permite transformar ab en bba.
La aplicación de una regla de reescritura u\to v sobre una palabra w consiste en encontrar una ocurrencia de u en w y re-emplazarla por v. Lo denotamos de este modo: w_1\underline{u}w_2 \to_{u\to v} w_1\underline{v}w_2 resaltando así qué regla se está usando y en que parte de las palabras.
Ejemplo 2 La aplicación de la regla ab\to bba es posible sobre la palabra aabab en dos posiciones distintas porqué aabab contiene dos ocurrencias de ab. Por ejemplo, podemos denotar la aplicación de la regla ab\to bba en la primera ocurrencia de ab de esta manera a\underline{ab}ab\to_{ab\to bba} a\underline{bba}ab\ .
Sea R es un conjunto de reglas de re-escritura.
Con w\to_R w' denotamos que la palabra w se transforma en w' aplicando una de las reglas de R.
Con w\to_R^* w' denotamos que la palabra w se transforma en la palabra w' aplicando cero o más pasos de re-emplazo con reglas de R.
Con w\to_R^+ w' denotamos que la palabra w se transforma en la palabra w' aplicando uno o más pasos de re-emplazo con reglas de R.
Finalmente, con w\to_R^i w' denotamos que la palabra w se transforma en la palabra w' aplicando i pasos de re-emplazo con reglas de R.