Volumes horaires
- CM 16.5
- Projet -
- TD 15.0
- Stage -
- TP 1.5
- DS -
Crédits ECTS
Crédits ECTS 3.0
Objectif(s)
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.
Responsable(s)
Lionel RIEG
Contenu(s)
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
néant
Contrôle 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
Informations complémentaires
Code de l'enseignement : 3MMTL1
Langue(s) d'enseignement : 
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