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.

  • $\begingroup$ Note that a mapping from $\Sigma^*$ to ${\mathcal P}(\Delta^*)$ and a relation on $\Sigma^*\times \Delta^*$ are usually considered equivalent. $\endgroup$ – Hendrik Jan May 30 '14 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Tim May 30 '14 at 5:03
  • $\begingroup$ @Tim Still, it happens one symbol at a time. $\endgroup$ – Yuval Filmus May 30 '14 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.