Let $\Sigma_1, \Sigma_2$ be alphabets. A substitution is a function $s:\Sigma_1^* \to P(\Sigma_2^*)$ such that

• $s$ preserves the empty word: $s(\lambda)=\lbrace \lambda \rbrace$ , and
• $s$ preserves concatenation: $s(\alpha\beta)=s(\alpha)s(\beta)$ .

The word ``substitution'' is used so often in mathematics, that substitution in the context of formal language theory is also known as a string substitution.

As the semigroup $\Sigma_1^*$ is freely generated by $\Sigma_1$ , every substitution $s:\Sigma_1^* \to P(\Sigma_2^*)$ is uniquely determined by its restriction to $\Sigma_1$ . Conversely, every function $f:\Sigma_1 \to P(\Sigma_2^*)$ extends uniquely to a substitution $f_s:\Sigma_1^* \to P(\Sigma_2^*)$ .

For any language $L\subseteq \Sigma_1^*$ and a substitution $s:\Sigma_1^* \to P(\Sigma_2^*)$ , define $$s(L):=\bigcup \lbrace s(u)\mid u\in L\rbrace.$$

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

• regular languages,
• context-free languages, and
• type-0 langauges.

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

Remark. A substitution $s$ is said to have property $\mathcal{P}$ if for each $a\in \Sigma$ , the set $s(a)$ has property $\mathcal{P}$ . 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...

Bibliography

1

S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).

2

D. C. Kozen, Automata and Computability, Springer, New York (1997).