Fichiers de cours de Théorie des langages

Aux étudiants de la deuxième année, nous proposons ce module d'informatique fondamentale. Il est centré autour de l'étude des aspects mathématiques des langages. En passant par la définition des systèmes générateurs (grammaires) et reconnaisseurs (automates) de certains classes de langages (Hiérarchie de Chomsky), nous y prouvons également les principales propriétés d'équivalence (Kleene) et de fermeture. Cette théorie est indispensable à tout informaticien. Elle trouve des applications dans divers domaines (synthèse de circuits, vérifications de protocoles, recherche de motifs, différentes phases d'analyse dans les compilateurs, etc.) 
Teacher: Slimane Oulad-Naoui

----------------------------------------------

 Présentation de la matière File

Volume + Évaluation

Plan & références

----------------------------------------------

 Rappel File

Rappel de qlq notions élémentaires en Math. 

Ensembles, relations, fonctions, logique

Graphes, Schémas de preuves

----------------------------------------------

Introduction aux langages

 Alphabet et mots

Langages

Grammaires 

----------------------------------------------

Langages réguliers

    Automates finis déterministes

 Automates finis non déterministes 

 Automates finis non déterministes avec epsilon-transitions File

 Expressions régulières (rationnelles) File

 Langages réguliers (reconnaissables) et théorème de kleene File

 Propriétés de fermeture des langages réguliers et lemme de pompage 

Minimisation 

Vous pouvez signaler n’importe quel lien cassé