substitution
Definition
Let be alphabets. A substitution, or string substitution, is a function such that
-
•
preserves the empty word: , and
-
•
preserves concatenation: .
In other words, for every word over , is a language over . In the second condition above, is the concatenation of languages: .
For example, suppose . The map taking to , where is obtained from by replacing every occurrence of by is a substitution.
One easy way to obtain more examples of substitutions is to start with some function
and extend it to all of by language concatenation: if , with , defining
gives us a substitution . It is easy to see that the extension is unique (if and both extend , then ).
In fact, every substitution is obtained this way: every substitution is the extension of its restriction to . This can be verified directly, but is the result of a more general fact: any function , where is a semigroup, extends uniquely to a semigroup homomorphism where is the semigroup freely generated by .
In the previous example, is the extension of the function that takes to and to .
Closure under Substitution
For any language and a substitution , define
A family of languages is said to be closed under substitutions if, given any substitution , with and for each , we have . The following families are closed under substitutions:
- •
- •
-
•
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 -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 , then is a word that is obtained from by replacing every occurrence of in by .
However, this is not always the case. For example, let , and be the map that takes to , where is obtained from by replacing all occurrences of , if any, by . Then it is easy to see that is not a substitution, for
while
Nevertheless, is “intuitively” a “substitution”.
-
•
A substitution is said to have property if for each , the set has property . Thus, for example, a substitution is finite if is a finite set, regular if is a regular language, and -free if each is -free, etc…
References
- 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).
Title | substitution |
---|---|
Canonical name | Substitution |
Date of creation | 2013-03-22 18:55:12 |
Last modified on | 2013-03-22 18:55:12 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 20 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 68Q45 |
Synonym | string substitution |
Related topic | HomomorphismOfLanguages |
Related topic | SubstitutionsInLogic |
Defines | -free substitution |
Defines | regular substitution |