## Polynomial size test sets for context-free languages.(English)Zbl 0834.68065

Summary: 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 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 [J. Albert, K. Culik II and J. Karhumaeki, Inf. Control 52, 172-186 (1982; Zbl 0522.68064)] and single exponential one from J. Karhumäki, W. Rytter and S. Jarominek [Theor. Comput. Sci. 116, 305-316 (1993; Zbl 0793.68090)]. On the other hand, we show that the lower bound for the problem is $$Q (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)$$.

### MSC:

 68Q45 Formal languages and automata

### Citations:

Zbl 0522.68064; Zbl 0793.68090
Full Text: