Formal Language Theory Meets Modern NLP
arXiv:2102.10094
Abstract
NLP is deeply intertwined with the formal study of language, both conceptually and historically. Arguably, this connection goes all the way back to Chomsky's Syntactic Structures in 1957. It also still holds true today, with a strand of recent works building formal analysis of modern neural networks methods in terms of formal languages. In this document, I aim to explain background about formal languages as they relate to this recent work. I will by necessity ignore large parts of the rich history of this field, instead focusing on concepts connecting to modern deep learning-based NLP.
arXiv comment24 pages, tutorial document. Updated based on feedback received
References in corpus (9)
- Visualizing and Understanding Recurrent Networks
- Theoretical Limitations of Self-Attention in Neural Sequence Models
- An Exponential Learning Rate Schedule for Deep Learning
- Asymmetric Valleys: Beyond Sharp and Flat Local Minima
- Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages
- Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
- On the Linguistic Capacity of Real-Time Counter Automata
- A Survey of Neural Networks and Formal Languages
- Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results