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

AbstractWe present a simple construction of linear size test sets for regular languages and of single exponential test sets for context-free languages. In the case of regular sets the size of our test set is exactly the number of transitions of the automaton. This improves the best-known upper bounds: exponential for regular and doubly exponential for context-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 given to test the equivalence of two deterministic gsm's as well as that of two deterministic finite transducers