Abstract We introduce NL∗, a learning algorithm for inferring non-deterministic fifinite-state automata using membership and equivalence queries. More specifically, residual fifinite-state automata (RFSA) are learned similarly as in Angluin’s popular L∗ algorithm, which, however, learns deterministic fifinitestate automata (DFA). Like in a DFA, the states of an RFSA represent residual languages. Unlike a DFA, an RFSA restricts to prime residual languages, which cannot be described as the union of other residual languages. In doing so, RFSA can be exponentially more succinct than DFA. They are, therefore, the preferable choice for many learning applications. The implementation of our algorithm is applied to a collection of examples and confifirms the expected advantage of NL∗ over L