Historically, grammatical inference [1]} has been at the core of formal language theory and could be considered to be fundamental in understanding important properties of natural languages.
A summary of much of the theoretical work done in formal languages can be found in [2]}.
Applications of formal language work have led to the development of methods for predicting and understanding sequences in diverse areas, such as financial time series, genetics and bioinformatics, and software data exchange [3]}, [4]}, [5]}.
Many artificial neural network (ANN) models take the form of a first order recurrent neural network (RNN) and are taught to learn context free and context-sensitive counter languages [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]}, [14]}, [15]}, [14]}, [17]}. However, from a theoretical perspective, RNNs augmented with an external memory have historically been shown to be more capable of recognizing context free languages (CFLs), such as with a discrete stack [18]}, [19]}, [20]}, or, more recently, with various differentiable memory structures [21]}, [22]}, [23]}, [24]}, [25]}, [26]}, [27]}, [28]}, [29]}, [30]}. Despite the positive recognition results, prior work on CFLs was unable to show model generalization beyond the training dataset, highlighting a troubling difficulty in training these kinds of networks. In contrast, [25]} and [6]} demonstrated that their RNN models could potentially generalize beyond the training dataset on simple CFLs.
