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 2016-2017

  • Bruno Bogaert (responsable du module)
  • Thomas Pietrzak
  • Yves Roos
  • Sylvain Salvati
  • 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

Langages rationnels

Langages algébriques

Corrigé d'évaluation

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.