# What can be said in general about a homomorphism between two regular languages?

In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can find a homomorphisms? And if not that, are there maybe a finite number of families of homomorphisms which divide all regular languages into classes?

My motivation for asking this question is from taking an undergrad course in group theory, and wanting to see if the treatment of polynomials by group theory can be applied to regular languages.

• Do you allow deleting homomorphisms? – Raphael Feb 19 '16 at 12:45
• Could you be a little clearer about the division into classes you are looking for? Existence of a homomorphism is not a symmetric property, are you thinking about the equivalence relation generated by it? – Klaus Draeger Feb 19 '16 at 12:46
• @Raphael since I'm interested in the most general answer, then, sure, (and especially since I think this is going to help to find more homomorphisms) :) – wvxvw Feb 19 '16 at 12:48
• @KlausDraeger I have to admit that I didn't consider the asymmetry. I'll need to think about it before I have a good answer. – wvxvw Feb 19 '16 at 12:49
• Are you familiar with the more algebraic side of language theory? Eilenberg's Variety Theorem, for example? (See e.g. coalg.org/calco15/slides/4.pdf) – Klaus Draeger Feb 19 '16 at 15:36

• For an infinite family of languages with no homomorphisms between them, consider the languages $L_k=\{a,a^k\}\subseteq\{a\}^*$ for $k\ge 2$. If $f:L_i\to L_j$ were a homomorphism for $i\neq j$, then $f(a)$ would be either $a$ or $a^j$, and $f(a^i)$ would be $a^i$ or $a^{ij}$, neither of which is in $L_j$.
• On the other hand, it is easy to find infinite chains of languages with homomorphisms between them, just consider $L_i=\{a^k\ |\ 1\le k\le i\}\subseteq\{a\}^*$ and the inclusion $L_i\to L_j$ for $i<j$.