Density of regular language containing all squares

Question

I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.

Suppose we have a regular language $L \subseteq \{0,1\}^*$ and the language $ \mathbf{S} = \{uu: u\in \{0,1\}^*\}$ is a subset of $L$. Clearly for even $n$ there are at least $2^{n/2}$ words of length $n$ in $L$. How would I show that there are at least $a2^n$ length $n$ binary words in $L$, for infinitely many $n$? Where $a$ is some constant that can depend on $L$.

Clearly $\mathbf{S}$ is non-regular, so there must be more length $n$ words accepted, but I am not sure how to get $\Theta(2^n)$ length $n$ words. Somehow one has to use the regularity of $L$, so maybe take its finite automaton, and relate the number of words to states/transitions? I don't see a way to proceed.

Answer 1

Suppose that the Myhill–Nerode relation of $L$ has the equivalence classes $C_1,\ldots,C_m$. Let $N_i(n) = |C_i \cap \{0,1\}^n|$. If $x,y \in C_i \cap \{0,1\}^n$ then $x^2,y^2 \in \mathbf{S} \subseteq L$, and so $xy,yx \in L$ since $C_i$ is an equivalence class. Therefore $$ |L \cap \{0,1\}^{2n}| \geq \sum_{i=1}^m N_i(n)^2. $$ Since the function $x^2$ is convex, the right-hand side is minimized (under the constraint $\sum_i N_i(n) = 2^n$) when all $N_i(n)$ are equal. Therefore $$ |L \cap \{0,1\}^{2n}| \geq m (2^n/m)^2 = \frac{2^{2n}}{m}. $$

---

The same argument works if we replace $\mathbf{S}$ with similar languages. Suppose for example that $L$ contains the language of all palindromes $\mathbf{P}$. If $x,y \in C_i \cap \{0,1\}^n$ then $yy^R \in \mathbf{P} \subseteq L$, and so $xy^R \in L$. Just as before, this shows that $|L \cap \{0,1\}^{2n}| \geq 2^{2n}/m$.

Furthermore, for each letter $\sigma \in \{0,1\}$, we have $y\sigma y^R \in L$, and so $x\sigma y^R \in L$. Therefore $$ |L \cap \{0,1\}^{2n+1}| \geq \sum_{i=1}^m 2N_i(n)^2 \geq 2m(2^n/m)^2 = \frac{2^{2n+1}}{m}. $$ In total, we get, for all $n$, $$ |L \cap \{0,1\}^n| \geq \frac{2^n}{m}. $$

---

Consider now the language $L_k$ of all words in which the first $k$ letters are the same as the last $k$ letters, reversed. This language has $m = \Theta(4^k)$ equivalence classes, contains all large enough palindromes, and has density $1/2^k = \Theta(1/\sqrt{m})$. This suggests the following vague question:

What is the minimal density of a regular language having $m$ equivalence classes and containing all palindromes or all squares?