POLYNOMIAL SIZE TEST SETS FOR CONTEXT-FREE LANGUAGES

We prove that each context-free language possesses a test set of size O(m(6)), where m is the number of productions in a grammar-producing t he language. A context-free grammar generating the test set can be fou nd in polynomial time by a sequential algorithm. It improves the doubl y exponential upper bound from [2] and single exponential one from J. Karhumaki, W. Rytter, and S. Jarominek (Theoret. Comput. Sci. 116 (199 3), 305-316). On the other hand, we show that the lower bound for the problem is Omega(m(3)) and that the lower bound for the size of a test set for a language defined over n-letter alphabet is Omega(n(3)). (C) 1995 Academic Press, Inc.