Let _ and _ be alphabets. A function h: _____* is a homomorphism.
A homomorphism is also tacitly understood to serve as a function h: _* ___* as determined by letter-by-letter extension inductively defined by h(_) = _, and h(x _) = h(x) h(_) for all x ____* and _ ____.
Finally, homomorphisms may be applied to languages, h: p(_*) __p(_*) , by the element-wise extension h(L) = {h(x) | x _ L} for each L ___*.
Note: p(S) is the collection of all subsets of set S
| Previous slide | Next slide | Back to first slide | View graphic version |