# Regular languages of finite index

Ex from Shallit. Let $L\subseteq \Sigma^*$ be a language. If $k\geq 1$ is s.t. $L^{k-1}\neq L^{k}=L^{k+1}$ say that $L$ has finite index equal to $k$. Then for every $k\geq 1$ there exists a regular language of finite index equal to $k$.

Proof. Fix $k\geq 1$ and pick $\Sigma$ such that $|\Sigma| = k$.
Let $L_{\leq 1}\subseteq \Sigma^*$ be the language of words containing at most one distinct letter in $\Sigma$. This is a regular language. Then $L^i=L_{\leq i}$ is the language of words containing at most $i$ distinct letters in $\Sigma$. Since $|\Sigma|=k$ one has that $L^{i-1} \neq L^i \neq L^{i+1}$ for every $1 < i < k$ but $L^{k}=L^{k+1}$. Q.E.D.