Recent work on differentiable stacks (the stackRNN) [1]}, which is closely related to this work, tested models on real natural language modeling tasks and on learning simple algorithmic patterns. These models were able to solve problems which required counting as well as memorization. Other work related to differentiable memory [2]} was motivated by the neural pushdown automaton, i.e., the NNPDA [3]}, [4]}, [5]}, [6]}, which extended RNNs to use an unbounded external differentiable memories such as stacks, queues, and doubly-linked lists. However, the computational limitations of these models were, unfortunately, only explored on synthetic datasets. Furthermore, none of the these models were tested on complex CFLs and the internal hidden representations were never analyzed in an effort to understand the internal network dynamics. Other memory-augmented models have also been proposed to solve CFLS, such as neural random access memory (NRAM) [7]} and the neural Turing machine (NTM) [8]}, but these models face a plethora of instability issues due to their structure and are quite difficult and expensive to train for real world problems. While NTMs and LSTMs were tested on Dyck (\(D_1\) ) languages over longer sequences and shown to be able to perfectly learn \(D_1\) , these results, however, are limited given that a \(D_1\)  language can also be easily learned by a counting model or counting automaton.
To truly test the generalization ability of first order RNNs and other memory-augmented models, one should test on more complex CFLs such as the Dyck languages.
Recently, a much more powerful and interpretable model, known as the neural state pushdown neural network (NSPDA), was proposed, demonstrating strong generalization on the Dyck (\(D_2\) ) languages [9]} while first order RNNs struggled when attempting to recognize more complex CFLs.
Unfortunately, due to the fact that the NSPDA makes heavy use of higher order weights, it would still be an expensive model to train on real world datasets, much like its ancestor, the NNPDA. To complement the rich body of historical work that has aimed to explore RNN performance on CFL recognition [9]}, [11]}, [12]}, [13]}, [1]}, we offer additional evidence of the limitations of first order RNNs in recognizing Dyck languages (\(D_>1)\) , strongly demonstrating the need for memory structures when attempting to learn recursive languages. We circumvent the limitations of the NSPDA's expensive training by crafting five different models and their training schemes for recognizing long strings generated by complex CFLs.
