  Studying language models (LMs) in terms of well-understood formalisms allows
us to precisely characterize their abilities and limitations. Previous work has
investigated the representational capacity of recurrent neural network (RNN)
LMs in terms of their capacity to recognize unweighted formal languages.
However, LMs do not describe unweighted formal languages -- rather, they define
\emph{probability distributions} over strings. In this work, we study what
classes of such probability distributions RNN LMs can represent, which allows
us to make more direct statements about their capabilities. We show that simple
RNNs are equivalent to a subclass of probabilistic finite-state automata, and
can thus model a strict subset of probability distributions expressible by
finite-state models. Furthermore, we study the space complexity of representing
finite-state LMs with RNNs. We show that, to represent an arbitrary
deterministic finite-state LM with $N$ states over an alphabet $\alphabet$, an
RNN requires $\Omega\left(N |\Sigma|\right)$ neurons. These results present a
first step towards characterizing the classes of distributions RNN LMs can
represent and thus help us understand their capabilities and limitations.
