Langages formels

• Formule: 2h, semestre d'automne
• Enseignant: Aris Xanthos
• Prérequis: aucun

Objectif
Ce cours propose une introduction à la théorie des langages formels et ses implications pour l'informatique théorique (décidabilité, complexité, etc.) et la linguistique (grammaticalité, analyse morphologique et syntaxique, etc.)

Contenu
Typologie et propriétés des langages, grammaires et automates; décidabilité et complexité; analyse formelle des langues naturelles.

Public
Master

Références
- Linz P. (2012). An Introduction to Formal Languages and Automata (Fifth Edition). Sudbury (MA): Jones & Bartlett Learning.
- Hopcroft J.E. & Ullman J.D. (1969). Formal Languages and their Relation to Automata. Boston (MA): Addison-Wesley Longman Publishing Company.
- Chomsky N. (1969). Structures syntaxiques. Paris: Seuil.
- Chomsky N. & Miller G.A. (1968). L'analyse formelle des langues naturelles. Paris: Mouton/Gauthier-Villars.
- Roche E. & Schabes Y. (1997). Finite-State Language Processing. Cambridge (MA): MIT Press.