4
$\begingroup$

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

$\endgroup$
0

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Why does the subset statement $\{ 0^m : m \ge M_0 \} \subseteq L^*$ provide enough information to state that $L^*$ is regular? $\endgroup$ Sep 2, 2018 at 20:11
  • $\begingroup$ I think I've worked out a specific case on my own, but was curious if that's a proven statement somewhere. $\endgroup$ Sep 2, 2018 at 20:31
  • $\begingroup$ If a unary language consists of all inputs of length $\ell$ and above, then it is accepted by the regular expression $0^\ell0^*$. $\endgroup$ Sep 3, 2018 at 1:16
1
$\begingroup$

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.

$\endgroup$

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.