Regular language superset with exactly exponential size

Question

Definitions

Define the density $\rho_L$ of a language $L$ to be a function $\rho_L : \mathbb{N} \rightarrow \mathbb{N}$ where $\rho_L(n)$ is the number of words in $L$ of length $n$.

Question

Let $L \subseteq \Sigma^*$ be a regular language with density $\rho_L(n) \leq b^n$ for some constant $b \in \mathbb{N}$ with $b \leq |\Sigma|$. Does there always exist another regular language $L' \subseteq \Sigma^*$ such that $\rho_{L'}(n) = b^n$ and $L \subseteq L'$?

Easy Cases

• $b=0$: Trivial.
• $b=1$: In this case $L$ has at most 1 word of each length. We first make a new language $X$, which is $L$, but where every character is replaced with $x$. Then, $L'=(x^* \setminus X) \cup L$ is a superset of $L$ with density function $\rho_{L'}(n)=1^n=1$ as desired, and it is regular via closure properties of regular languages.
• $b=|\Sigma|$: Here $L' = \Sigma^*$ always works.

So the first interesting case is $b=2, |\Sigma|=3$.

Answer 1

The answer is "no". Let $L$ be an arbitrary regular language such that $\rho_L(n) \leq b^n$ with $b \leq |\Sigma|$. Assume there exists such a regular language $L'$ with $L \subseteq L'$ and $\rho_{L'}(n) = b^n$. Then, by closure properties of regular languages, the language $L' \setminus L$ is also regular, with density $\rho_{L'\setminus L}(n) = b^n - \rho_L(n)$. Then, as shown in "On the generating sequences of regular languages on $k$-symbols" by Beal and Perrin, 2003, this suffices to prove that $\rho_L$ is the density of some other regular language $L''$ defined over a different alphabet of size $b$. But this implication is false: in the referenced paper, the authors give an example of a regular language $L$ satisfying $\rho_L(n) \leq b^n$ such that there is no regular language with the same density defined over an alphabet of size $b$. So we have reached a contradiction, and the answer to the original question is "no".