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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.