  We present an algorithm for extraction of a probabilistic deterministic
finite automaton (PDFA) from a given black-box language model, such as a
recurrent neural network (RNN). The algorithm is a variant of the
exact-learning algorithm L*, adapted to a probabilistic setting with noise. The
key insight is the use of conditional probabilities for observations, and the
introduction of a local tolerance when comparing them. When applied to RNNs,
our algorithm often achieves better word error rate (WER) and normalised
distributed cumulative gain (NDCG) than that achieved by spectral extraction of
weighted finite automata (WFA) from the same networks. PDFAs are substantially
more expressive than n-grams, and are guaranteed to be stochastic and
deterministic - unlike spectrally extracted WFAs.
