5
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you allow deleting homomorphisms? $\endgroup$
    – Raphael
    Commented Feb 19, 2016 at 12:45
  • $\begingroup$ 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? $\endgroup$
    – Klaus Draeger
    Commented Feb 19, 2016 at 12:46
  • $\begingroup$ @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) :) $\endgroup$
    – wvxvw
    Commented Feb 19, 2016 at 12:48
  • $\begingroup$ @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. $\endgroup$
    – wvxvw
    Commented Feb 19, 2016 at 12:49
  • 1
    $\begingroup$ 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) $\endgroup$
    – Klaus Draeger
    Commented Feb 19, 2016 at 15:36

1 Answer 1

Reset to default
5
$\begingroup$

Some examples, to get the discussion going:

  • 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$.
Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ OK, I see now. Perhaps a better characteristic then would be, when comparing languages: "how much should be done to fix the language(s) in order for there to be a homomorphism between them?". So that the question would be more of a "how different two languages are?", something like Levenshtein distance. $\endgroup$
    – wvxvw
    Commented Feb 19, 2016 at 14:17
  • 1
    $\begingroup$ That does sound like an interesting direction. Of course, getting the details right (so that they also make sense for infinite languages) is the tricky part. $\endgroup$
    – Klaus Draeger
    Commented Feb 19, 2016 at 15:22
  • 1
    $\begingroup$ Whatever this turns out with, it is definitely a new question (or three). $\endgroup$
    – vonbrand
    Commented Feb 21, 2016 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.