Théorie des langages 1 - 3MMTL1

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

Le cours est programmé dans ces filières :

• Cursus ingénieur - Tronc Commun - Semestre 5

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

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

• Equipe Algorithmique-Mathématiques discrètes
• Equipe Bases théoriques de l'informatique

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

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