substitution

Definition

Let ${\mathrm{\Sigma }}_1,{\mathrm{\Sigma }}_2$ be alphabets. A substitution, or string substitution, is a function $s:{\mathrm{\Sigma }}_1^{*}\to P({\mathrm{\Sigma }}_2^{*})$ such that

• $s$ preserves the empty word: $s(\lambda )=\{\lambda \}$, and

• $s$ preserves concatenation: $s(\alpha \beta )=s(\alpha )s(\beta )$.

In other words, for every word $\alpha$ over ${\mathrm{\Sigma }}_1$, $s(\alpha )$ is a language over ${\mathrm{\Sigma }}_2$. In the second condition above, $s(\alpha )s(\beta )$ is the concatenation of languages: $\{uv\mid u\in s(\alpha ),v\in s(\beta )\}$.

For example, suppose $\mathrm{\Sigma }=\{a,b\}$. The map $s$ taking $u$ to $\{u^{\prime }\}$, where $u^{\prime }$ is obtained from $u$ by replacing every occurrence of $a$ by $b$ is a substitution.

One easy way to obtain more examples of substitutions is to start with some function

$$f:{\mathrm{\Sigma }}_1\to P({\mathrm{\Sigma }}_2^{*}),$$

and extend it to all of ${\mathrm{\Sigma }}_1^{*}$ by language concatenation: if $u=a_1\mathrm{\cdots }{a}_n$, with $a_i\in {\mathrm{\Sigma }}_1$, defining

$$s(u):=f(a_1)\mathrm{\cdots }f(a_n)$$

gives us a substitution $s$. It is easy to see that the extension is unique (if $s_1$ and $s_2$ both extend $f$, then $s_1=s_2$).

In fact, every substitution is obtained this way: every substitution $s:{\mathrm{\Sigma }}_1^{*}\to P({\mathrm{\Sigma }}_2^{*})$ is the extension of its restriction to ${\mathrm{\Sigma }}_1$. This can be verified directly, but is the result of a more general fact: any function $f:A\to B$, where $B$ is a semigroup, extends uniquely to a semigroup homomorphism $f^{*}:A^{*}\to B$ where $A^{*}$ is the semigroup freely generated by $A$.

In the previous example, $s$ is the extension of the function that takes $a$ to $\{b\}$ and $b$ to $\{b\}$.

Closure under Substitution

For any language $L\subseteq {\mathrm{\Sigma }}_1^{*}$ and a substitution $s:{\mathrm{\Sigma }}_1^{*}\to P({\mathrm{\Sigma }}_2^{*})$, define

$$s(L):=\bigcup \{s(u)\mid u\in L\}.$$

A family $ℱ$ of languages is said to be closed under substitutions if, given any substitution $s$, with $L\in ℱ$ and $s(w)\in ℱ$ for each $w\in L$, we have $s(L)\in ℱ$. The following families are closed under substitutions:

• regular languages,

• context-free languages, and

• type-0 langauges.

As a corollary, the families of regular, context-free, and type-0 languages are closed under homomorphisms, since every homomorphism of languages is really just a special case of substitution, such that every symbol of the domain alphabet is mapped to a singleton consisting of a word over the range alphabet.

The family of context-sensitive languages is not closed under general substitutions. Instead, it is closed under $\lambda$-free substitutions (see remark below).

Remarks.

• The notion of string substitution generally corresponds to our intuitive notion of how a substitution should behave:

  given words $u,v,w$, then $\mathrm{Substitute}(u,v,w)$ is a word that is obtained from $u$ by replacing every occurrence of $v$ in $u$ by $w$.

  However, this is not always the case. For example, let $\mathrm{\Sigma }=\{a,b\}$, and $s$ be the map that takes $u$ to $\{u^{\prime }\}$, where $u^{\prime }$ is obtained from $u$ by replacing all occurrences of $aa$, if any, by $b$. Then it is easy to see that $s$ is not a substitution, for

  $$s(a)s(a)=\{a\}\{a\}=\{aa\}$$

  while

  $$s(aa)=\{b\}\ne s(a)s(a).$$

  Nevertheless, $s$ is “intuitively” a “substitution”.

• A substitution $s$ is said to have property $𝒫$ if for each $a\in \mathrm{\Sigma }$, the set $s(a)$ has property $𝒫$. Thus, for example, a substitution $s$ is finite if $s(a)$ is a finite set, regular if $s(a)$ is a regular language, and $\lambda$-free if each $s(a)$ is $\lambda$-free, etc…