1. A particular kind of mapping on formal languages. Let Σ1 and Σ2 be alphabets. For each symbol a in Σ1 let s(a) be a Σ2-language. The function s is a substitution. A homomorphism occurs where each s(a) is a single word. s is Λ-free if no s(a) contains the empty word.
The function s can be extended to map Σ1-words to Σ2-languages:
i.e. the concatenation of the languages
s(
a1),…,
s(
an).
s can then be further extended to map Σ
1-languages to Σ
2-languages:
s(
L) is called the
substitution image of
L under
s.
2. See substitution cipher.