vskarleas/inf302

INF302 - Languages et automates

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) - Trouver le repertoire sur mon compte

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 :
• Apprendre à analyser des propriétés (correction, terminaison, coût) des algorithmes (en relation avec l'UE INF231).
• Apprendre à analyser formellement les propriétés d'un langage.