|
Pervasive in mathematical linguistics and computer science, (formal) languages present many interesting and difficult problems. Various mathematical theories have been developed to deal with them. Of particular importance is the classification of languages in various classes of interest, such as regular, context-free, context-sensitive, recursive, and recursively enumerable (the Chomsky hierarchy), but also many others such as the ubiquitous P and NP. Various tools have been introduced to recognize languages, such as automata and semigroups. In the case of regular languages, there is a rather successful classification using syntactic semigroups, as developed by Eilenberg in the 1970's. Beyond regular languages, this approach fails. In this talk, we explain why this is the case and the role played by topology in the classification of languages. We also argue that this difficulty can be overcome by a compactification of minimal automata, viewed as suitable algebraic structures.
|
