Homomorphism - Homomorphisms and E-free Homomorphisms in Formal Language Theory

Homomorphisms and E-free Homomorphisms in Formal Language Theory

Homomorphisms are also used in the study of formal languages (although within this context, often they are briefly referred to as morphisms). Given alphabets and, a function h : → such that for all u and v in is called a homomorphism (or simply morphism) on . Let e denote the empty word. If h is a homomorphism on and for all in, then h is called an e-free homomorphism.

This type of homomorphism can be thought of as (and is equivalent to) a monoid homomorphism where the set of all words over a finite alphabet is a monoid (in fact it is the free monoid on ) with operation concatenation and the empty word as the identity.

Read more about this topic:  Homomorphism

Famous quotes containing the words formal, language and/or theory:

    “True variety is in that plenitude of real and unexpected elements, in the branch charged with blue flowers thrusting itself, against all expectations, from the springtime hedge which seems already too full, while the purely formal imitation of variety ... is but void and uniformity, that is, that which is most opposed to variety....”
    —Marcel Proust (1871–1922)

    “A mind enclosed in language is in prison.”
    —Simone Weil (1909–1943)

    “Lucretius
    Sings his great theory of natural origins and of wise conduct; Plato
    smiling carves dreams, bright cells
    Of incorruptible wax to hive the Greek honey.”
    —Robinson Jeffers (1887–1962)