Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

Question

We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can be generated just by concatenating $0^9$. Hence we can represent $L^*$ using a FSM.

My Question :

1. Here I got these numbers $120$–$128$ for $m^2$ by trial and error. Is there any formal method to arrive at these numbers?

2. If we consider $m^2$ to be a function such that we get $L^*$ is regular, will it also be regular for $m^3$?

Answer 1

Consider the language $$ L = \{ 0^{m^k} : m \geq m_0 \}. $$ Since $m_0$ and $m_0+1$ are relatively prime, so are $m_0^k$ and $(m_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m_0^k$ and $(m_0+1)^k$, implying that $$L^* \supseteq \{ 0^m : m \geq M_0 \}$$ for some $M_0$, and so $L^*$ is regular. Using the classical formula of the coin problem applied to $m_0^k$ and $(m_0+1)^k$, we can upper bound the optimal value of $M_0$ by $$ M_0 \leq (m_0^k-1)((m_0+1)^k-1). $$ For example, the case considered in your post has $k=2$ and $m_0=3$, and this gives the bound $M_0 \leq (3^2-1)(4^2-1) = 120$, which is (apparently) tight in this case.

Recently it has been shown that it is $\Sigma_2^P$ hard to determine the largest integer which cannot be represented as a non-negative combination of given positive integers (Matsubara 2016), though in your particular case the set $\{ m^k : m \geq m_0 \}$ has a lot of structure, and so the problem might be feasible.

Answer 2

If a language contains $(0^n | 0^m)^*$ with gcd (n, m) = 1, then every integer $k ≥ n \cdot m$ is the sum of multiples of n and m, so the language contains $(0^k)$, $k ≥ n \cdot m$.

This is the case here because gcd ($3^2$, $4^2$) = gcd (9, 16) = 1, so the language contains $0^k$, $k≥144$. And it contains a few more strings $O^k$. And that is a regular language. (In this case, the language actually contains $0^k$, $k≥88$).

If you had a different language L, using terms $m^k$, $m ≥ m_0$ with large k and $m_0$ instead of $m^2$ for $m≥3$, then finding the exact grammar that demonstrates L is regular might be quite hard to find, but the argument above shows that it exists.