# Regular language superset with exactly exponential size

### 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$$.

• What have you tried? Commented Jun 18, 2022 at 21:44
• @Nathaniel I've tried just using closure properties of regular languages combined with the fact that $\Sigma^*$ is regular (along with any subset of $\Sigma$), but that really only works if $b = |\Sigma|$.
– Jake
Commented Jun 19, 2022 at 3:58
• Given a regular language $L$ such that $\rho_L(n) \leq b^n$. Does there always exist a regular language with density $b^n - \rho_L(n)$ on an alphabet with $b$ letters? This would allow a similar construction as your $b=1$ case. Commented Jun 23, 2022 at 10:19
• @Janmar No: there exist regular languages $L$ with $\rho_L(n) \leq b^n$ such that no regular language exists with density $b^n - \rho_L(n)$, even without the $b$-letter alphabet restriction. See "On the generating sequences of regular languages on k-symbols" by Beal and Perrin, 2003, Theorem 3.2 and the preceding counterexample.
– Jake
Commented Jun 23, 2022 at 16:52

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".