A regular language over an alphabet is locally testable if, loosely speaking, testing whether or not an arbitrary word (over ) is in is completely determined by its subwords of some fixed length. The name locally testable comes from the fact that properties of , and not , determine the membership of in .
To formalize this notion, we first define, for any word over , the set of all subwords of
of length , where is a symbol not in .
Definition. We say that a regular language is -testable if for any such that
we have iff . The equation above says three things at once:
the set of subwords of of length is equal to the set of subwords of of length ,
the prefix of of length is equal to the prefix of of length , and
the suffix of of length is equal to the suffix of of length .
We say that is locally testable if it is -testable for some .
If we denote the family of all -testable languages, and the family of all locally testable languages, then
Note that there are only two -testable languages: and .
We only sketch the proof here. For the first assertion, note that for every ,
In addition, the language is -testable but not -testable. For the second statement, note that is not definite for any . On the other hand, a finite language containing a single word of length is not -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 including , is closed under complementation and intersection, and hence all Boolean operations. The star-closure of is , the family of all regular languages.
- 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
|Date of creation||2013-03-22 18:59:03|
|Last modified on||2013-03-22 18:59:03|
|Last modified by||CWoo (3771)|