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 $$\#u\#$$ 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 $$\operatorname{sw}_k(u)=\operatorname{sw}_k(v),$$ 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$ .

If we denote the family of all $k$ -testable languages, and the family of all locally testable languages, then

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

Proposition 1   Let be the family of definite languages. Then

1. for any $k\ge 0$ , and the inclusion is strict.
2. and are not comparable for any $k> 0$ . In other words, for every $k$ , there is a $k$ -testable language that is not definite, and a definite language that is not $k$ -testable.
3. , and the inclusion is strict.

We only sketch the proof here. For the first assertion, note that for every $k\ge 0$ , $$\operatorname{sw}_{k+1}(u)=\operatorname{sw}_{k+1}(v)\quad\mbox{implies}\quad \operatorname{sw}_k(u)=\operatorname{sw}_k(v).$$ In addition, the language $\lbrace ab^k\rbrace^*$ is $(k+1)$ -testable but not $k$ -testable. For the second statement, note that $\lbrace ab^k\rbrace^*$ is not definite for any $k\ge 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 provide us with an example of an infinite chain of subfamilies of the family of regular languages.

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

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

Bibliography

1

A. Salomaa, Formal Languages, Academic Press, New York (1973).