HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canhomomorphismwhatlanguagesregulargeneralsaidtwobetweenabout

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#53334, answer score: 5

Revisions (0)

No revisions yet.