Homomorphism

Introduction: A homomorphism is a function that maps strings to strings and that respects string concatenation. In other words, if h : Σ∗ → Γ∗ is ahomomorphism that takes strings from some alphabet Σ to stringsin an alphabet Γ (not necessarily distinct), then it must satisfy twoconditions:

• h(ε) = ε

• For string s = xy in Σ∗, h(xy) = h(x)h(y). In other words, the result of applying h to s is the same as the result of concatenatingthe application of h to its pieces x and y.

To obtain a better appreciation for the fact that a homomorphism “respects string concatenation,” let us consider something that is nota homomorphism—say g. Let Σ = {a, b, c, d} and Γ = {0, 1, 2}.

• g(abcd) = 0

• g(ab) = 1

• g(cd) = 1

• g(s) = 2, for all other strings.

g is not a homomorphism because g(abcd) = 0 while g(ab)g(cd) is 11.

Ensuring homomorphisms

How do we ensure that a given function on strings is a homomorphism? The most commonly used approach to ensure that something is a homomorphism is to specify a mapping that goes from symbols to strings, and then to “lift” it up to map from strings to strings. Let h’be thesymbol to string map, with signature

h’: Σ ∪ {ε} → Γ∗,

and define h using h’. Here is an example. Let h’be as follows:

Formally, h(s) is defined in terms of h’as follows:

• If length(s) > 1, then let x _= ε and y _= ε be such that s = xy. Then, h(s) = h(x)h(y).
• If length(s) = 1, then h(s) = h’(s).

Now, by definition, h respects string concatenation and all works out well! Homomorphisms can also be defined over languages in a straightforward manner. Given L,

h(L) = {y | h(x) = y for some x in L}.

Inverse homomorphism

Given a homomorphism h, an inverse homomorphism h⁻¹maps a string y to the maximal set of strings that y could have come from; formally:

h⁻¹(y) = {x | h(x) = y}.

Example:Consider h to be

Then, h⁻¹(012) = {abc, abd} because 2 could have come either from c or from d. Inverse homomorphisms can also be defined over languagesin a straightforward manner. Given L,

h⁻¹(L) = ∪y∈L h⁻¹(y).

In other words, for each y ∈ L, take h⁻¹(y), and then take the union of all these sets.