Université Lyon 1
Université de Lyon
Arqus
Accueil  >>  Licence  >>  Informatique  >>  Informatique  >>  Théorie des langages formels
  • Domaine : Licences du domaine SCIENCES, TECHNOLOGIES, SANTE
  • Diplôme : Licence
  • Mention : Informatique
  • Parcours : Informatique
  • Unité d'enseignement : Théorie des langages formels
Nombre de crédits de l'UE : 3
Code APOGEE : INF3038L
UE Libre pour ce parcours
UE valable pour le semestre 1 de ce parcours
    Responsabilité de l'UE :
BRANDEL SYLVAIN
 sylvain.brandeluniv-lyon1.fr
04.72.44.82.42
    Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
9 h
Travaux Pratiques (TP)
6 h
Durée de projet en autonomie de l'étudiant (PRJ)
0 h
Durée du stage
0 h
Effectifs Cours magistraux (CM)
210 étudiants
Travaux dirigés (TD)
35 étudiants
Travaux pratiques (TP)
18 étudiants

* Ces horaires sont donnés à titre indicatif.

    Pré-requis :
Il est recommandé d'avoir suivi les UE Algorithmique et programmation récursive (en L1) et programmation fonctionnelle (en L2)
    Compétences attestées (transversales, spécifiques) :
- Notions d'alphabet, de mots, de langages.
- Langages rationnels : automates à états finis déterministes et non déterministes, déterminisation, langages rationnels, lemme de l'étoile, minimisation des automates (théorème de Myhill - Nerode), grammaires régulières, expressions régulières.
- Langages algébriques : grammaires, langages générés par une grammaire, grammaires et langages algébriques, automates à pile déterministes et non déterministes, lemme de la double étoile.
- Hiérarchie des langages : langages rationnels, hors contextes, dépendants du contexte, récursifs, récursivement énumérables.
- Problématique de la compilation, analyse lexicale, analyse syntaxique.
    Programme de l'UE / Thématiques abordées :

L'objectif de cette UE est double.
D'une part cette UE apporte des connaissances en informatique théorique et fondamentale, à travers l'étude des langages rationnels et algébriques, des automates à états finis et à pile, illustrés de preuves de théorèmes de rationalité ou non, d'algébricité ou non, ainsi que de minimisation des états. L'UE prépare ainsi au module de modèles de calculs qui introduira les machines de Turing en M1.
D'autre part, des TP permettent d'illustrer les concepts théoriques, en montrant l'implémentation et le fonctionnement pratique des automates introduits de manière formelle. Les TP sont effectués à l'aide de l'assitant à la preuve Coq, qui permet, en adéquation avec le module logique classique, d'implémenter les automates et les grammaires avec le langage Gallina, puis de faire des preuves d'équivalences entre automates et grammaires.
Une introduction à l'analyse lexicale et syntaxique permettra également de préparer au module de compilation en M1.

    Liste des autres Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 06/07/2017
SELECT * FROM parcours INNER JOIN ue_parcours ON PAR_ID_FK=PAR_ID INNER JOIN mention ON MEN_ID = PAR_MENTION_FK WHERE PAR_ACTIVATE = 0 AND UE_ID_FK='8163' ORDER BY UE_ID_FK ASC, PAR_ID_FK ASC