closure under homomorphism

A homomorphism is a find-and-replace rule for symbols. You fix, for each letter of the alphabet, a fixed string to swap it with — then you apply that swap to EVERY symbol of a string, in order, and glue the results together. Replacing 'a' with '01' and 'b' with the empty string ε (epsilon) turns aba into 01 01, that is 0101. It is just a systematic translation, symbol by symbol.

Formally a homomorphism h sends each symbol of an alphabet Σ (Sigma) to a string over some alphabet (possibly a different one), and extends to whole strings by h(s1 s2 ... sn) = h(s1) h(s2) ... h(sn), with h of the empty string being empty. For a language L, its image h(L) is { h(w) : w in L } — translate every string in the language. The closure claim is: if L is regular, then h(L) is regular too. The construction is direct — in a regular expression for L, replace every occurrence of each symbol x by the regular expression for h(x); the result denotes h(L). (There is also closure under INVERSE homomorphism, h^{-1}(M) = { w : h(w) in M }, proved on automata.)

Homomorphisms are the bridge that lets you reuse hard-won facts across alphabets, and they are a sharp non-regularity tool. Because regular languages are closed under homomorphism, if applying or un-applying a homomorphism to a candidate language would produce a known non-regular language, the candidate cannot be regular either. Note that one symbol may map to a multi-symbol string or to ε, so a homomorphism can lengthen, shorten, or even erase parts of strings — it is not merely a one-to-one renaming.