<p>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).</p>

CC BY-SA 3.0
2013-10-18T14:36:26.570Z
thx for your answer. one question related, what about prefix-closed languages, do you have there a counter-example too?
StefanH
CC BY-SA 3.0
2013-10-16T15:53:40.947Z
2013-10-16T15:53:40.947Z
J.-E. Pin
<p>Let $L$ be an infinite regular language, then does there exists a strictly locally testable  infinite language $P$ such that $P \subseteq L$?</p>

CC BY-SA 3.0
2013-10-16T11:04:27.983Z
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
CC BY-SA 3.0
2013-10-16T11:21:32.153Z
yes, so it is quite trivial, I mean for every infinite $L$ if there exists an infinite $P$ which is locally testable.
StefanH
CC BY-SA 3.0
2013-10-16T11:41:40.253Z
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
CC BY-SA 3.0
2013-10-16T15:44:20.993Z
@phs $(ab)^+$ is strictly locally testable.
J.-E. Pin
<fl.formal-languages><automata-theory><regular-language>
Does every regular language contains a strictly locally testable language?
StefanH
# Does every regular language contains a strictly locally testable language?

(Asked by: username_0 on 2013-10-16)

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

**Tags:** fl.formal-languages, automata-theory, regular-language
> **Comments:**
> **username_1**: 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?  
> **username_0**: yes, so it is quite trivial, I mean for every infinite $L$ if there exists an infinite $P$ which is locally testable.  
> **username_1**: 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.  
> **username_2**: @phs $(ab)^+$ is strictly locally testable.  

---

## 1 answers

### Answer by username_2 on 2013-10-16. Score: 6 | Accepted answer

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).

> **Comments:**
> **username_0**: thx for your answer. one question related, what about prefix-closed languages, do you have there a counter-example too?  

---

