Skip to main content
deleted 1 character in body
Source Link
Klaus Draeger
  • 2.2k
  • 12
  • 17

Some examples, to get the discussion going:

  • For an infinite family of languages with notno 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$.

Some examples, to get the discussion going:

  • For an infinite family of languages with not 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$.

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$.
Source Link
Klaus Draeger
  • 2.2k
  • 12
  • 17

Some examples, to get the discussion going:

  • For an infinite family of languages with not 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$.