Efficient constructions of test sets for regular and context-free languages (Q685373)

This paper involves a nice contribution to a formal language theory. It has been known (Ehrenfeucht conjecture) that, for any language \(L\), there exists a finite test set \(F_ L\) (for each pair of morphisms, if they agree on \(F_ L\), then they agree on the whole set \(L\)). Here, a simple construction of linear size test sets for regular languages and of single exponential test sets for context-free languages is presented. This essentially improves the best known upper bounds: exponential for regular and doubly exponential for context-free languages.