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

  • 1
    $\begingroup$ 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? $\endgroup$
    – phs
    Oct 16 '13 at 11:04
  • $\begingroup$ yes, so it is quite trivial, I mean for every infinite $L$ if there exists an infinite $P$ which is locally testable. $\endgroup$
    – StefanH
    Oct 16 '13 at 11:21
  • $\begingroup$ 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. $\endgroup$
    – phs
    Oct 16 '13 at 11:41
  • $\begingroup$ @phs $(ab)^+$ is strictly locally testable. $\endgroup$
    – J.-E. Pin
    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).

  • $\begingroup$ thx for your answer. one question related, what about prefix-closed languages, do you have there a counter-example too? $\endgroup$
    – StefanH
    Oct 18 '13 at 14:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.