En un sistema de reescritura de cadenas, ¿la reescritura 'consume' la cadena? Por ejemplo, supongamos que se escribe $101$ y hay una regla $1x1 \rightarrow 11x11,$ podemos aplicar esta regla para escribir $11011,$ pero ¿tenemos que tachar $101$?
Respuesta
¿Demasiados anuncios?
No, estamos interesados en el cierre transitivo de $\rightarrow$, es decir, lo que se puede derivar a partir de premisas dadas. No hay necesariamente borrado involucrado, solo elección no determinista. Por ejemplo, si tenemos las reglas $1x1 \rightarrow 11x11$ y $x0x \rightarrow x$ entonces tenemos $101 \rightarrow 11011$ por la primera regla y $101 \rightarrow 1$ por la segunda y las tres cadenas $(101, 11011, 1)$ son deducciones del sistema de reescritura de cadenas, por lo que no hay realmente ninguna sentido en que se tache la primera.
