A string rewriting system is a substitution system used to transform a given string according to specified rewriting rules.

Equivalence of basic string rewriting systems

---

Certain basic forms of string rewriting systems are essentially equivalent to term rewriting systems. Suppose we have strings over some alphabet A, and we are only given a list of transformation rules on substrings of the form

$x\_0x\_1\backslash cdots\; x\_n\; \backslash rightarrow\; y\_0y\_1\backslash cdots\; y\_m,\backslash quad\; x\_i,\; y\_i\; \backslash in\; A$

indicating that any substring x₀x₁...x_n is to be replaced with y₀y₁...y_m.

We can reformulate such a system into a term rewriting system -- the transformation rules now become

$x\_0(x\_1(\backslash cdots\; (\; x\_n(x)\; ))\; \backslash cdots\; )\; \backslash rightarrow\; y\_0(y\_1(\backslash cdots\; (y\_m(x))\; \backslash cdots),$

where each x_i and y_i constitute the function symbols in the term rewriting system.

Strings in this term rewriting systems are then ground terms.

Examples

---

Examples of computational models based on deterministic string rewriting include Markov algorithms, Post canonical systems (e.g., tag systems), a variety of formal grammars, and L-systems (the latter lending themselves well to the creation of certain types of fractals such as the Cantor set and Menger sponge).

See also

---

• Formal grammar
• L-system
• Markov algorithm
• Semi-Thue system
• Tag system

Computational models | Theory of computation