Mathematical Foundations
Leonor Becerra-Bonache, Gemma Bel-Enguix, M. Dolores Jiménez‐López, Carlos Martı́n-Vide · 2018
This chapter provides an overview of classical formal language theory. The text is focused on the definition of the fundamental concepts of language, grammar, and automata, and introduces some basic related notions. We also present the hierarchical classification of formal grammars proposed by N. Chomsky in the 1950s, known as the Chomsky hierarchy. The location of natural languages in this hierarchy is also discussed, together with the concept of Mildly Context Sensitivity. In the last part of the chapter, other formalisms that have interesting linguistic and computational properties are briefly introduced. The chapter concludes with a short review of grammatical inference, a subfield of machine learning that deals with the process of learning grammars and languages from data.