Does there exist a language L over an alphabet Σ such that for all homomorphisms h : Σ* → Σ* there exists a string x ∈ L for which |h(x)| ≤ |x|?
Asked
Active
Viewed 154 times
1
-
Isn't letterwise duplication a homomorphism? Or did I misinterpret the question (which in my understanding actually does not parse grammatically: what is the predicate following "such that")? – Hagen von Eitzen Jun 05 '19 at 20:07
-
@HagenvonEitzen You are correct, it was a typo. Does it make more sense now? – Karlberg Jun 05 '19 at 20:34
-
Is $\Sigma$ finite and $L$ countable? – R. Burton Jun 05 '19 at 21:56
-
@R.Burton Σ is finite, not sure if L is countable – Karlberg Jun 05 '19 at 22:39
1 Answers
2
Yes, any language containing the empty word $1$, since $h(1) = 1$ by definition of a morphism. Thus $|h(1)| = |1| = 0$.
J.-E. Pin
- 40,163