We continue the study of combinatorial property testing, initiated by Goldr
eich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653-750]. The subject
of this paper is testing regular languages. Our main result is as follows.
For a regular language L is an element of {0,1}* and an integer n there exi
sts a randomized algorithm which always accepts a word w of length n if w i
s an element of L and rejects it with high probability if w has to be modif
ied in at least epsilonn positions to create a word in L. The algorithm que
ries (O) over tilde (1/epsilon) bits of w. This query complexity is shown t
o be optimal up to a factor polylogarithmic in 1/epsilon. We also discuss t
he testability of more complex languages and show, in particular, that the
query complexity required for testing context-free languages cannot be boun
ded by any function of epsilon. The problem of testing regular languages ca
n be viewed as a part of a very general approach, seeking to probe testabil
ity of properties defined by logical means.