Back to Home

---

title: “Langages et Automates” layout: page —

Langages et Automates

Description du Cours

Ce cours aborde les concepts fondamentaux des langages formels et des automates. Il couvre les tâches d’analyse d’un compilateur, la notion de grammaire, d’analyse syntaxique, et inclut une étude approfondie des langages rationnels et des automates.

Plan du Cours

WK 1: Introduction

• Les tâches d’analyse d’un compilateur.
• La notion de grammaire et d’analyse syntaxique.
• Durée: 1h30 lecture, 1h30 TD/TP

WK 2-3: Langages rationnels

• Définitions.
• Opérations sur les mots et langages.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

WK 4-5: Automates - Définition et propriétés

• Définition d’un automate.
• Calculs et langage accepté.
• Propriété d’un automate.
• Complétion.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

WK 6-7: Synchronisation et déterminisation d’un automates

• Synchronisation.
• Langage accepté.
• Déterminisation.
• Algorithme.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

WK 8-10: Constructions d’automates pour des langages donnés

• Constructions simples.
• Transformation d’automates.
• Automate pour le complémentaire.
• Automate miroir.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

WK 11-12: Lemme de l’étoile et Théorème de Kleene

• Le lemme de l’Etoile pour les grammaires régulières.
• Théorème de Kleene.
• Automate de Thompson.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

WK 13-14: Automates

• Lemme d’Arden.
• Résolution système d’équations.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

WK 15-16: Automates minimal

• Définitions.
• Automate des résiduels.
• Équivalence de Nérode.
• Automate quotient.
• Durée: 1h30 lecture, 1h30 TD/TP chaque semaine

Matériel de Cours

Cours Magistraux (CM)

• Langage Formel CM1
• Langage Formel CM2
• Langage Formel CM3
• Langage Formel CM4