EFFICIENT CONSTRUCTIONS OF TEST SETS FOR REGULAR AND CONTEXT-FREE LANGUAGES

We present a simple construction of linear size test sets for regular languages and of single exponential test sets for context-free languag es. In the case of regular sets the size of our test set is exactly th e number of transitions of the automaton. This improves the best-known upper bounds: exponential for regular and doubly exponential for cont ext-free languages. We give also an O(n log n) time algorithm for the morphism equivalence and an O(n3 log n) time algorithm to test the gsm equivalence on a regular language. An O(n2 log n) time algorithm is g iven to test the equivalence of two deterministic gsm's as well as tha t of two deterministic finite transducers.