Vous êtes ici : FIL > Portail > Licence Info > L3S5 Info > AEL

Automates et Langages

Ce cours est une introduction aux outils formels pour l'informatique et en particulier à la théorie des langages, et aux notions de calcul et de décidabilité.

Contenu

  • Langages rationnels et expressions régulières. Manipulation d'outils utilisant ces expressions (egrep, JLex, ...).
  • Langages reconnaissables, automates finis de mots déterministes et non-déterministes. Déterminisation, minimalisation.
  • Théorème de Kleene.
  • Les grammaires, la hiérarchie de Chomsky.
  • Les langages algébriques et les automates à pile.
  • Les machines de Turing et la notion de problème décidable.

Équipe pédagogique 2017-2018

  • Bruno Bogaert (responsable du module)
  • Dimitri Gallois
  • Thomas Pietrzak
  • Yves Roos
  • Alexandre Sedoglavic
  • Marie-Émilie Voge
Adresses e-mail : Prénom.Nom@univ-lille1.fr

Volume horaire

Volume horaire de présence : 48 heures se décomposant en 18 heures de cours et 36 heures de TD (dont 18 sur ordinateur).

Crédits ECTS

5 crédits.

Transparents du cours

Les slides du cours ne comportent, pour l'essentiel, que l'énoncé formel des définitions et propriétés abordées dans le cadre du cours. Les exemples, explications plus informelles, ainsi que les preuves sont présentés oralement ou au tableau lors des séances en amphi.

Langages rationnels

Langages algébriques

TD sur machine

L'évaluation s'effectue suivant une procédure de contrôle continu. Trois notes (échelle de 20) seront attribuées à chaque étudiant durant le semestre :

  • TP : la note issue des mini-projets traités en TD sur machines.
  • Interros : la note issue des évaluations « flash » réalisées en amphi.
  • DS : la note du devoir surveillé de fin de semestre.

Note finales

  • 1ère session

    N = (TP + sup(Interros, DS) + 2 * DS) /4

  • 2ème session

    N = (TP + 3 * DS)

    où DS désigne ici la note du DS de rattrapage

L'unité acquise apporte 5 ECTS.