Informations Générales

Travail encadré : 60 heures

Travail personnel conseillé : 60 heures

ECTS : 6

Mots Clés :

• Automates : 
• définition : syntaxe et sémantique
• déterminisme et non-déterminisme, déterminisation.
• opérations de composition des automates
• expression d'algorithmes (actions, contrôle, configurations, traces), correction.
• Langages réguliers : reconnaissance par un automate d'états fini, propriétés algébriques, problèmes de décision, constante d'itération.
• Expressions régulières : définition (syntaxe et sémantique), théorème de Kleene, conversions entre automates et expressions régulières, lemme d'Arden.
• Grammaires régulières.
• Langages non-réguliers : lemme de l'itération.

Pré-requis pour cette UE : INF 201 (programmation fonctionnelle)

Programme résumé : Langages réguliers et automates d'états finis

• Reconnaissance d'un langage régulier par un automate d'états fini.
• Propriétés algébriques des langages réguliers (expression régulières, traduction vers et depuis des automates).
• Notion de non déterminisme (automates non-déterministes et avec epsilon-transitions), déterminisation d'un automate.
• Problèmes de décision : langage vide, langage infini.

Si le temps le permet : Définition inductive et preuve par induction

• Théorème de Kleene et points fixes
• Schéma de preuve par induction

Compétences visées :

• La maîtrise de la programmation s'appuie sur l'étude des langages et moyens d'expression utilisés en informatique et sur la compréhension des modèles de calcul sous-jacents.
• Les automates sont des structures finies qui permettent de décrire des phénomènes infinis, par exemple l'ensemble des comportements d´un programme ou l'ensemble des phrases d'un langage.
• La théorie des automates fait partie des fondements de l'informatique. Dans ce cours nous l'abordons avec les objectifs suivants :

1. Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF231).
2. Apprendre à analyser formellement les propriétés d'un langage.

Evaluation (version préliminaire) :

• CC1 : examen à mi-parcours (au milieu du semestre), coefficient 0,4
• CC2 : examens courts tout au long du semestre, coefficient 0,4
• EF : examen final lors de la semestre de partiels prévue à cet effet, coefficient 1,2 

La note finale est donc :

(0,4*CC1 + 0,4*CC2 + 1,2*EF)  /  2.