Sin embargo, cuando se combinan con un algoritmo apropiado, los sistemas de reescritura pueden verse como programas informáticos, y varios programas para demostrar teoremas[3] y lenguajes de programación declarativa se basan en la reescritura de términos.
) indica que una expresión que coincida con el lado izquierdo de la regla se puede reescribir como una formada por el lado derecho, y donde cada símbolo denota una subexpresión.
En tal sistema, cada regla se elige de para que el lado izquierdo sea equivalente al lado derecho y, en consecuencia, cuando el lado izquierdo coincida con una subexpresión, realizar una reescritura de esa subexpresión de la izquierda al derecho se mantiene la consistencia y el valor lógicos de toda la expresión.
Para hacer esto, cada uno de tales números debe codificarse como un término.
, donde A es una etiqueta de categoría sintáctica, como un sintagma nominal o una oración, y X es una secuencia de tales etiquetas o morfemas, expresando el hecho que A puede ser reemplazada por X al generar la estructura constitutiva de una oración.
significa que una oración (O) puede consistir en una sintagma nominal (SN) seguida de una sintagma verbal (SV); otras reglas especificarán en cuáles subconstituyentes puede consistir un sintagma nominal o verbal, y así sucesivamente.