# 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. – Hendrik Jan May 30 '14 at 7:04