Polynomial Size Test Sets For Context-Fr
β
J. Karhumaki; W. Plandowski; W. Rytter
π
Article
π
1995
π
Elsevier Science
π
English
β 648 KB
We prove that each context-free language possesses a test set of size \(O\left(m^{6}\right)\), 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 doubl