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:
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).
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
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…
- 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).
|Date of creation||2013-03-22 18:55:12|
|Last modified on||2013-03-22 18:55:12|
|Last modified by||CWoo (3771)|