Define functions ψ 1 , ψ 2 : Note that for all strings w 1 , w 2 ∈ Σ * , ψ(w 1 w 2 ) = ψ(w 1 )+ψ(w 2 ).
ψ is a homomorphism from the free monoid Σ * to Z × Z with addition as the monoid operation and (0, 0) as identity.