stylistic:tone, structural:reformatting
Formal language theory

Homomorphisms are also used in the study of formal languages and are often briefly referred to as morphisms. Given alphabets Σ 1 {\displaystyle \Sigma _{1}} and Σ 2 {\displaystyle \Sigma _{2}}, a function h: Σ 1 ∗ → Σ 2 ∗ {\displaystyle h\colon \Sigma _{1}^{*}\to \Sigma _{2}^{*}} such that h (u v) = h (u) h (v) {\displaystyle h(uv)=h(u)h(v)} for all u, v ∈ Σ 1 {\displaystyle u,v\in \Sigma _{1}} is called a homomorphism on Σ 1 ∗ {\displaystyle \Sigma _{1}^{*}}. If h {\displaystyle h} is a homomorphism on Σ 1 ∗ {\displaystyle \Sigma _{1}^{*}} and ε {\displaystyle \varepsilon } denotes the empty string, then h {\displaystyle h} is called an ε {\displaystyle \varepsilon } -free homomorphism when h (x) ≠ ε {\displaystyle h(x)\neq \varepsilon } for all x ≠ ε {\displaystyle x\neq \varepsilon } in Σ 1 ∗ {\displaystyle \Sigma _{1}^{*}}.

A homomorphism h: Σ 1 ∗ → Σ 2 ∗ {\displaystyle h\colon \Sigma _{1}^{*}\to \Sigma _{2}^{*}} on Σ 1 ∗ {\displaystyle \Sigma _{1}^{*}} that satisfies | h (a) | = k {\displaystyle |h(a)|=k} for all a ∈ Σ 1 {\displaystyle a\in \Sigma _{1}} is called a k {\displaystyle k} -uniform homomorphism. If | h (a) | = 1 {\displaystyle |h(a)|=1} for all a ∈ Σ 1 {\displaystyle a\in \Sigma _{1}} (that is, h {\displaystyle h} is 1-uniform), then h {\displaystyle h} is also called a coding or a projection.

The set Σ ∗ {\displaystyle \Sigma ^{*}} of words formed from the alphabet Σ {\displaystyle \Sigma } may be thought of as the free monoid generated by Σ {\displaystyle \Sigma }. Here the monoid operation is concatenation and the identity element is the empty word. From this perspective, a language homomorphism is precisely a monoid homomorphism.