Editing Homomorphism (section)

==Formal language theory==
Homomorphisms are also used in the study of [[formal language]]s<ref>{{cite book |first=Seymour |last=Ginsburg |author-link=Seymour Ginsburg |title=Algebraic and automata theoretic properties of formal languages |publisher=North-Holland |year=1975 |isbn=0-7204-2506-9}}</ref> and are often briefly referred to as ''morphisms''.<ref>{{cite book |first1=T. |last1=Harju |first2=J. |last2=Karhumӓki |chapter=Morphisms |title=Handbook of Formal Languages |volume=I |editor1-first=G. |editor1-last=Rozenberg |editor2-first=A. |editor2-last=Salomaa |publisher=Springer |year=1997 |isbn=3-540-61486-9}}</ref> Given alphabets <math>\Sigma_1</math> and <math>\Sigma_2</math>, a function <math>h \colon \Sigma_1^* \to \Sigma_2^*</math> such that <math>h(uv) = h(u) h(v)</math> for all <math>u,v \in \Sigma_1</math> is called a ''homomorphism'' on <math>\Sigma_1^*</math>.<ref group="note">The ∗ denotes the [[Kleene star]] operation, while Σ<sup>∗</sup> denotes the set of words formed from the alphabet Σ, including the empty word. Juxtaposition of terms denotes [[concatenation]]. For example, ''h''(''u'') ''h''(''v'') denotes the concatenation of ''h''(''u'') with ''h''(''v'').</ref> If <math>h</math> is a homomorphism on <math>\Sigma_1^*</math> and <math>\varepsilon</math> denotes the empty string, then <math>h</math> is called an <math>\varepsilon</math>''-free homomorphism'' when <math>h(x) \neq \varepsilon</math> for all <math>x \neq \varepsilon</math> in <math>\Sigma_1^*</math>.

A homomorphism <math>h \colon \Sigma_1^* \to \Sigma_2^*</math> on <math>\Sigma_1^*</math> that satisfies <math>|h(a)| = k</math> for all <math>a \in \Sigma_1</math> is called a <math>k</math>''-uniform'' homomorphism.{{sfn|Krieger|2006|p=287}} If <math>|h(a)| = 1</math> for all <math>a \in \Sigma_1</math> (that is, <math>h</math> is 1-uniform), then <math>h</math> is also called a ''coding'' or a ''projection''.{{citation needed|reason=Give an example citation for each synonym.|date=July 2022}}

The set <math>\Sigma^*</math> of words formed from the alphabet <math>\Sigma</math> may be thought of as the [[free monoid]] generated by {{nowrap|<math>\Sigma</math>.}} 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.<ref group=note>We are assured that a language homomorphism ''h'' maps the empty word ''ε'' to the empty word. Since ''h''(''ε'') = ''h''(''εε'') = ''h''(''ε'')''h''(''ε''), the number ''w'' of characters in ''h''(''ε'') equals the number 2''w'' of characters in ''h''(''ε'')''h''(''ε''). Hence ''w'' = 0 and ''h''(''ε'') has null length.</ref>