In this paper, we unravel a fundamental connection between weighted finite
automata~(WFAs) and second-order recurrent neural networks~(2-RNNs): in the
case of sequences of discrete symbols, WFAs and 2-RNNs with linear activation
functions are expressively equivalent. Motivated by this