# Differences between substitution and rewriting?

I am continuing with my self-study of formal languages.

Given two alphabets $\Sigma$ and $\Delta$, a string substitution is a mapping from $\Sigma$ to $\mathcal P(\Delta^*)$, which induces a mapping from $\Sigma^*$ to $\mathcal P(\Delta^*)$.

In case that a string substitution is a string homomorphism, it is a mapping from $\Sigma$ to $\Delta^*$, which induces a mapping from $\Sigma^*$ to $\Delta^*$.

A rewriting system, however, seems to be a relation on $\Sigma^* \times \Delta^*$.

So I wonder if the main difference between rewriting and substitution is that rewriting is a relation, which might not be a mapping, while substitution is a mapping? Thanks.

• Note that a mapping from $\Sigma^*$ to ${\mathcal P}(\Delta^*)$ and a relation on $\Sigma^*\times \Delta^*$ are usually considered equivalent. Commented May 30, 2014 at 7:04

There are three differences between substitutions and rewriting systems:

1. Substitutions happen one symbol at a time, while a rewrite rule can rewrite an entire substring at once.
2. Substitution is a single-valued function while in a rewriting system, several rewriting rules can apply to any given substring.
3. A substitution must specify what value is substituted for each symbol. Rewriting systems need not apply in all situations.

I would say that the first two are the major differences. You can define substitutions so that they are partial functions, and then the third difference doesn't apply.

• Thanks. "Substitutions happen one symbol at a time", but they can induce a mapping that can apply to a string at a time, by concatenation?
– Tim
Commented May 30, 2014 at 5:03
• @Tim Still, it happens one symbol at a time. Commented May 30, 2014 at 5:24
• Interesting answer. I can ask this as a separate question or you can clarify in this answer. How are substitution and rewriting different with regards to commutativity and associativity? E.g. Substitution for multiple variables does not, in general, commute. from nLab Commented Feb 2, 2022 at 10:23
• For those like me writing code to implement substitution and stuck on understanding Composition of substitutions for more detail and some examples start here on slide 7. Commented Feb 2, 2022 at 10:31
• It's better to ask this as a separate question. Commented Feb 2, 2022 at 21:13