Learning to Decide a Formal Language: A Recurrent Neural Network Approach
Krsto Proroković

Abstract:
We use recurrent neural networks (RNNs) for deciding locally k-testable languages. We show that, when used for deciding languages, RNNs fail to generalise to unseen examples. However, using attention greatly improves the generalisation. We then implement a differentiable version of the scanner used for deciding locally k-testable languages. We show that RNNs are able to store the k-factors in its memory but not arrange then as a look-up table which is necessary for deciding languages specified by multiple k-factors.