Polynomial Size Test Sets For Context-Free Languages

AbstractWe prove that each context-free language possesses a test set of size O(m6), where m is the number of productions in a grammar-producing the language. A context-free grammar generating the test set can be found in polynomial time by a sequential algorithm. It improves the doubly exponential upper bound from [2] and single exponential one from J. Karhumäki, W. Rytter, and S. Jarominek (Theoret. Comput. Sci.116 (1993), 305-316). On the other hand, we show that the lower bound for the problem is Ω(m3) and that the lower bound for the size of a test set for a language defined over n-letter alphabet is Ω(n3)