Languages that are recognizable by first order RNNs, as well as the limits of their computational power, are still being explored. [1]} recently theoretically demonstrated the expressiveness of RNNs with finite precision under asymptotic conditions. They showed that RNNs and those that use gated recurrent units (GRUs) work reasonably well on regular grammars while long short-term memory (LSTM) can recognize real-time counter languages such as \(a^nb^n\)  or \(a^nb^nc^n\)  as well as variations. Empirically, LSTM RNNs have demonstrated the capability to recognize simple context free languages (such as \(a^nb^n\) ) and context-sensitive languages (such as \(a^nb^nc^n\) ) by using a complex counting mechanism [2]}, [3]} where as GRUs struggle to perform dynamic counting [3]}.
While some of the languages from the Chomsky hierarchy [5]} can be modelled based on counting, counting does not capture the actual structural property underlying natural languages – formal languages are hierarchically structured [5]}, [7]}. As a result, hierarchy creates a deeply nested structured yielding what is known as the strictly context free languages (CFLs).
To recognize these CFLs, a simple counting mechanism is not sufficient and, as a result, a stack is necessary in order to correctly recognize these grammars. Based on formal language theory, Dyck languages \(D_n\) , where \(n>1\) , are similar to CFLs[8]}.
[9]} showed that first order RNNs, e.g., GRU, LSTM, perform well on Dyck languages (\(D_1)\)  and its various combinations, when \(n=1\) . However, these models struggle whenever \(n\)  is increased. In theory, a pushdown automaton with a stack can correctly recognize any CFG which is also known to be the homomorphic image of a regular \(D_n\)  language [10]}, [7]}.
