Vous êtes ici

  1. Accueil
  2. UE6 - Langages formels

UE6 - Langages formels

UE6 - Langages formels

En pratique :

Volume horaire de cours : 20
Volume horaire global de TD : 20
Langue principale : français

Description du contenu de l'enseignement

Dans ce cours sont définis les mots, les langages et les opérations sur ces objets. Les langages étudiés sont essentiellement les langages rationnels et algébriques. Différentes approches coexistent pour décrire un langage : il peut être reconnu par un automate, engendré par une grammaire, dénoté par une expression rationnelle, solution d'un système d'équations ; on s'attache à montrer l'équivalence de ces modes de description, par des manipulations sur ces outils eux-mêmes. Au travers des manipulations formelles sur les langages rationnels et algébriques, on vise également une meilleure compréhension du niveau d'expressivité de chacun de ces types de langage.

  1. Introduction : la théorie des langages et ses applications en informatique
  2. Le monoïde libre
  3. Engendrer des mots, des langages : les grammaires algébriques
  4. Reconnaître des mots, des langages : les automates finis
  5. Langages reconnaissables, opérations sur ces langages
  6. Langages rationnels et théorème de Kleene
  7. Automate minimal
  8. Formes de grammaires algébriques
  9. Automates à pile et modes de reconnaissance associés
  10. Lemme d'itération pour les langages algébriques
  11. La hiérarchie de Chomsky
  12. Décidabilité : problèmes décidables et indécidables en théorie des langages

 


Compétences à acquérir

L’objectif principal de ce cours est une bonne prise en main des diverses définitions de « langage » au sens informatique. La rigueur des descriptions est fondamentale.

  • À la fin du cours, les étudiants savent décrire de plusieurs manières (par une grammaire, un automate, …) l’ensemble des mots constituant un langage formel.
  • Ils savent identifier la classe d’un langage donné (rationnel ou algébrique)
  • Ils savent juger si une description formelle est conforme ou non à la description proposée en langage naturel.
  • Ils ont amélioré la clarté et la rigueur de leur expression écrite.
  • Ils ont amélioré leur capacité d’abstraction.
  • Ils ont appréhendé la notion de décidabilité, ils connaissent quelques limites de l’informatique.

 


Bibliographie, lectures recommandées

  • Mathématiques pour l’informatique, André Arnold et Irène Guessarian (Dunod, 4ème édition 2005), 300 exercices corrigés
  • Méthodes mathématiques pour l’informatique, Jacques Vélu, (Dunod, 5ème édition 2013)
  • Théorie des langages et des automates, Jean-Michel Autebert (Dunod, 1997)
  • Introduction to automata theory, languages and computation, J.E. Hopcroft, J.D. Ullman (Addison-Wesley, 2007)
  • Introductory Logic and Sets for Computer Scientists, N. Nissanke (Addisson Wesley, 1998)
  • Concepts fondamentaux de l’informatique, A. Aho, J. D. Ullman (Dunod, 1996)
  • Langages algébriques, J.M. Autebert (Masson, 1987)
  • Le Théorème de Gödel, Ernest Nagel (Seuil, 1997)
  • La machine de Turing, A. Turing, J-Y. Girard (Seuil, 1999)
  • GODEL, ESCHER, BACH. Les Brins d’une Guirlande Eternelle, Douglas Hofstadter (InterEditions, 1985 - Dunod, 2008)

Pré-requis

Pré-requis obligatoires

Le prérequis est deux années d’études post baccalauréat S, comportant des aspects théoriques (dont quelques outils formels). De solides bases de mathématiques (telles que la maîtrise de la preuve par récurrence) sont indispensables, même si elles ne sont pas directement exploitées. L’étudiant doit être doté d’une bonne capacité d’abstraction.