Traditional recurrent neural networks (RNNs) have a fixed, finite number of
memory cells. In theory (assuming bounded range and precision), this limits
their formal language recognition power to regular languages, and in practice,
RNNs have been shown to be unable to learn many context-free languages (CFLs).
In order to expand the class of languages RNNs recognize, prior work has
augmented RNNs with a nondeterministic stack data structure, putting them on
par with pushdown automata and increasing their language recognition power to
CFLs. Nondeterminism is needed for recognizing all CFLs (not just deterministic
CFLs), but in this paper, we show that nondeterminism and the neural controller
interact to produce two more unexpected abilities. First, the nondeterministic
stack RNN can recognize not only CFLs, but also many non-context-free
languages. Second, it can recognize languages with much larger alphabet sizes
than one might expect given the size of its stack alphabet. Finally, to
increase the information capacity in the stack and allow it to solve more
complicated tasks with large alphabet sizes, we propose a new version of the
nondeterministic stack that simulates stacks of vectors rather than discrete
symbols. We demonstrate perplexity improvements with this new model on the Penn
Treebank language modeling benchmark.

通过给循环神经网络增加非确定性堆栈数据结构，可以扩展循环神经网络的语言识别能力，识别上下文无关语言和更多的非上下文无关语言，同时提高信息容量，这可以通过模拟向量堆栈来实现。