Université Lyon 1
Arqus
Accueil  >>  Licence  >>  Informatique  >>  Informatique et mathématiques  >>  Théorie des langages formels
  • Domaine : Licences du domaine SCIENCES ET TECHNOLOGIES
  • Diplôme : Licence
  • Mention : Informatique
  • Parcours : Informatique et mathématiques
  • 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.43.14.34
    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 (PRJ)
0 h
Durée du stage
0 h
Effectif Cours magistraux (CM)
210 étudiants
Effectif Travaux dirigés (TD)
35 étudiants
Effectif 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.

Date de la dernière mise-à-jour : 06/07/2017
SELECT MEN_ID, `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`, `PAR_ID` 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 `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`