# Does every regular language contains a strictly locally testable language?

Let $L$ be an infinite regular language, then does there exists a strictly locally testable infinite language $P$ such that $P \subseteq L$?

• 0 down vote If $L$ is the empty language you need $P$ empty too. Luckily it is star-free. And works for other $L$. Or is your question different from what I understood?
– phs
Oct 16 '13 at 11:04
• yes, so it is quite trivial, I mean for every infinite $L$ if there exists an infinite $P$ which is locally testable. Oct 16 '13 at 11:21
• Now for $L=(ab)^*$, any regular $L'\subseteq L$ is some $\{(ab)^i~|~ i\in U\}$ for an ultimately periodic $U\subseteq\mathbb{N}$. It seems that this language is not star-free when $L'$, i.e. $U$, is infinite.
– phs
Oct 16 '13 at 11:41
• @phs $(ab)^+$ is strictly locally testable. Oct 16 '13 at 15:44

The answer is no. The argument was suggested by phs, but you have to start with a different language. Take $L = (aa)^*$. Then any regular language $K$ contained in $L$ is of the form $$K = \{(aa)^n \mid n \in U \}$$ for some ultimately periodic subset $U$ of $\mathbb{N}$. If $K$ is infinite, then the period $p$ of $U$ is not $0$ and thus $K$ is not star-free (hence not locally testable and not strictly locally testable).