Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Théorie des langages 1 - 3MMTL1

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Volumes horaires

    • CM : 16.5
    • TD : 15.0
    • TP : 1.5
    • Projet : -
    • Stage : -
    • DS : -
    Crédits ECTS : 3.0
  • Responsables : Lionel RIEG

Objectifs

Introduction aux formalismes utilisés pour la définition de la syntaxe des langages informatiques, étude de leurs propriétés et des outils servant à les manipuler.

Contenu

I - Introduction à la théorie des langages
Vocabulaire, mots, opérations sur les langages, notions sur l'induction
II - Langages réguliers
Automates finis, déterminisation, minimisation
Expressions régulières, équivalence des deux représentations
Propriétés de fermeture et existence de langages non réguliers ; lemme de l'étoile
III - Grammaires, hiérarchie de Chomsky
Manipulations de grammaires
Arbres de dérivation, ambiguïté
Preuves sur grammaires

Prérequis

néant

Contrôles des connaissances

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) : Projet

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) : Examen écrit
Salle spécifique :
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents papier
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : tout objet connecté
    Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : examen écrit
Salle spécifique :
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents papier
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : tout objet connecté
    Commentaires : examen écrit dans les mêmes conditions que la session normale, le contrôle continu est pris en compte

  • MCC en présence
    N1 = 1/4 contrôle continu + 3/4 examen écrit
  • MCC à distance
    N1 = 1/3 contrôle continu à distance + 2/3 (devoir à la maison ou examen en temps limité à la maison)
  • Seconde session
    N2 = 1/4 contrôle continu + 3/4 examen écrit de rattrapage

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Tronc Commun - Semestre 5
cf. l'emploi du temps 2023/2024

Informations complémentaires

Code de l'enseignement : 3MMTL1
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

P. Berlioux, M. Echenim, M. Lévy : Théorie des langages, polycopié Ensimag
J.E. Hopcroft, R. Motwani, J.D. Ullman : Introduction to Automata Theory, Languages, and Computation, 3/E, Addison-Wesley, 2006

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

mise à jour le 23 octobre 2023

Université Grenoble Alpes