A standard exercise in formal language theory uses Lagrange's four-square theorem to construct a language $L$ such that $L$ isn't regular but $L^2$ is regular. (Let $A = \{ a^{n^2} : n \geq 0 \}$. Then $A$ isn't regular, but $A^4 = \{ a^n : n \geq 0 \}$ is regular, hence either $L = A$ or $L = A^2$ fits the bill; in fact $A^2$ is not regular, so we must pick the latter.)

This answer generalizes this, constructing for every $m$ a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular, but $L^m,L^{m+1},\ldots$ are regular. This prompts the following definition:

The regularity profile of a language $L$ is $\rho(L) = \{ n \in \mathbb{N}_+ : L^n \text{ is regular} \}$.

My question is:

Which regularity profiles are achievable?

The answer mentioned above shows that $\{n : n \geq m \}$ is a regularity profile for every $m \geq 1$.

It is also easy to construct a language whose regularity profile is empty: $\{ a^{2^n} : n \geq 0 \}$.

Clearly every regularity profile is closed under addition: if $L^a,L^b$ are regular then so is $L^{a+b}$.

Is every subset of $\mathbb{N}_+$ which is closed under addition a regularity profile?

The question is interesting both for a general alphabet and for the special case of a unary alphabet.

  • $\begingroup$ Yuval, do you have an idea if these questions have been studied yet, or did they remain open? $\endgroup$ Commented Jan 14 at 17:57
  • 1
    $\begingroup$ @BaderAbuRadi I'm not aware of any progress on these questions, though I'm not sure I would know. Nobody contacted me regarding them. $\endgroup$ Commented Jan 15 at 18:05


Your Answer

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

Browse other questions tagged or ask your own question.