Théorie des langages 1 - 3MMTL1
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail
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érequisné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
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
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail
mise à jour le 23 octobre 2023