Let _ and _ be alphabets. A function s: ____p(_*) is a substitution (i.e., each letter of _ is associated with a language over _). A substitution is called regular if each of the languages s(_) is regular.
A substitution is also tacitly understood to serve as a function s: _* __p(_*) as determined by letter-by-letter extension inductively defined by s(_) = {_}, and s(x _) =s(x) s(_) for all x ____* and _ ____.
Finally, substitutions may be applied to languages, s: p(_*) __p(_*), by element-wise extension s(L) = ___ s(x).
x _ L
| Previous slide | Next slide | Back to first slide | View graphic version |