substitution

views updated

substitution
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: s(a1…an) = s(a1)…s(an)

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) = {s(w) | w ∈ L}

s(L) is called the substitution image of L under s.

2. See substitution cipher.

More From encyclopedia.com