A language L over an alphabet Σ such that for all homomorphisms h : Σ* → Σ* there exists a string x ∈ L for which |h(x)| ≤ |x|?

155 Views Asked by At

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|?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, any language containing the empty word $1$, since $h(1) = 1$ by definition of a morphism. Thus $|h(1)| = |1| = 0$.