Abstract
Nearly all algorithms for learning an unknown regular language, in particular the popular L? algorithm, yield deterministic finite automata. It was recently shown that the ideas of L? can be extended to yield non-deterministic automata, and that the respective learning algorithm, NL? , outperforms L? on randomly generated regular expressions. We conjectured that this is due to the existential nature of regular expressions, and NL? might not outperform L? on languages with a universal nature. In this paper we introduce UL? — a learning algorithm for universal automata (the dual of non-deterministic automata); and AL? — a learning algorithm for alternating automata (which generalize both universal and non-deterministic automata). Our empirical results illustrate the advantages and trade-offs among L? , NL? , UL? and AL? .