info205 - Automates et Langages

Credits

5

Prerequisites

Aucun

Parcours

• mandatory for the computer science mention of the "licence"
• proposée pour le parcours « Mathématique »

Objectives

Apprendre des démarches d'abstraction et de formalisation pour la conception et l'analyse de systèmes à travers l'étude de trois modèles de calculs : un modèle de machine à mémoire bornée, un modèle de description et d'analyse syntaxiques et un modèle général de calcul (les machines de Turing).

Organization

week

1

2

3

4

5

6

7

8

9

10

11

12

13

C (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TD (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TP (2h)

×

×

×

×

×

Student personal work

about 50h

Evaluation

• for UE without Labs : sup ( Ex, (2Ex + CC)/3)
• for UE with Labs : (2TP + 3 sup(Ex, (2Ex + CC)/3))/5

Contents

• Automates finis et expressions régulières : Opérations et algorithmes sur les automates. Déterminisation. Minimisation. Théorème de Kleene. Applications : Recherche de motif, modélisation de systèmes, analyse lexicale.
• Introduction aux grammaires non contextuelles : Notions de dérivation, d'arbre de dérivation, d'ambiguïté dans les grammaires algébriques. Grammaires régulières. Application : Conception de grammaires pour des langages typiques. Grammaires XML.
• Machines de Turing et calculabilité : Définition des machines de Turing. Notions de configurations et calculs. Calculabilité. Décidabilité. Application : Comprendre les limites de l'informatique. Indécidabilité de l'arrêt des programmes. Indécidabilité d'autres problèmes, en particulier sur les mots et les grammaires algébriques

Instructor(s)

Yves Roos

fichier source pour édition/modification