A regular language $L$ over an alphabet $\Sigma$ is locally testable if, loosely speaking, testing whether or not an arbitrary word $u$ (over $\Sigma$) is in $L$ is completely determined by its subwords of some fixed length. The name locally testable comes from the fact that properties of $u$, and not $L$, determine the membership of $u$ in $L$.

To formalize this notion, we first define, for any word $u$ over $\Sigma$, the set $\operatorname{sw}_{k}(u)$ of all subwords of

of length $k$, where $\#$ is a symbol not in $\Sigma$.

Definition. We say that a regular language $L$ is $k$-testable if for any $u,v\in\Sigma^{*}$ such that

we have $u\in L$ iff $v\in L$. The equation above says three things at once:

• the set of subwords of $u$ of length $k$ is equal to the set of subwords of $v$ of length $k$,

• the prefix of $u$ of length $k$ is equal to the prefix of $v$ of length $k$, and

• the suffix of $u$ of length $k$ is equal to the suffix of $v$ of length $k$.

We say that $L$ is locally testable if it is $k$-testable for some $k\geq 0$.

If we denote $\mathscr{T}(k)$ the family of all $k$-testable languages, and $\mathscr{T}(\infty)$ the family of all locally testable languages, then

Note that there are only two $0$-testable languages: $\Sigma^{*}$ and $\varnothing$.

We only sketch the proof here. For the first assertion, note that for every $k\geq 0$,

In addition, the language $\{ab^{k}\}^{*}$ is $(k+1)$-testable but not $k$-testable. For the second statement, note that $\{ab^{k}\}^{*}$ is not definite for any $k\geq 0$. On the other hand, a finite language containing a single word of length $k+1$ is not $k$-testable. The last assertion is a direct consequence of the second one.

Thus, the families $\mathscr{T}(k)$ provide us with an example of an infinite chain of subfamilies of the family of regular languages.

With regard to the closure properties in $\mathscr{T}(k)$, it is easily see that $\mathscr{T}(k)$ for all $k\geq 0$ including $k=\infty$, is closed under complementation and intersection, and hence all Boolean operations. The star-closure of $\mathscr{T}(\infty)$ is $\mathscr{R}$, the family of all regular languages.

Remark. Every locally testable language is star-free, but not conversely.