# Tag Info

2

Let us prove a more general result: For each $m \geq 2$ there is a language $L$ such that $L,L^2,\ldots,L^{m-1}$ are not regular but $L^m$ is regular. The language we construct will be unary, that is, of the form $L = \{a^n : n \in S\}$, where $S \subseteq \mathbb{N}$ is $$S = \{ km : k \geq 0 \} \cup \{ m^k + 1 : k \geq 1 \}.$$ Let $1 \leq p \leq m-1$,...

1

Unless you must deal with unary regular languages, there is no need for complex math ... Just pick an irregular language that is able to "capture and mask" the concatenation of itself; e.g. over $\Sigma = \{a,b \}$ $L = \{ (a^ib^j) (a^n b^n) \mid i, j \geq 1, n \geq 1\} \; \cup \;$ $\{ (a^ib^j)^k \mid i, j \geq 1, k \neq 2\}$ $LLLL$ is equal to ....

Only top voted, non community-wiki answers of a minimum length are eligible