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


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

  • 1
    $\begingroup$ What have you tried? $\endgroup$
    – Nathaniel
    Commented Jun 18, 2022 at 21:44
  • $\begingroup$ @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|$. $\endgroup$
    – Jake
    Commented Jun 19, 2022 at 3:58
  • $\begingroup$ 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. $\endgroup$
    – Janmar
    Commented Jun 23, 2022 at 10:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jake
    Commented Jun 23, 2022 at 16:52

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.