Introduction à la théorie des langages
Objectifs
Base de la théorie des langages et de ses interprétations en termes algorithmique et de représentation par automate..
- Savoir manipuler le concept de mots et les opérations sur les mots, manipuler le concept de langage et les opérations sur les langages.
- Savoir identifier les langages que l’on peut reconnaître avec un automate d’états finis.
- Pour un langage rationnel donné, savoir passer du modèle automate au modèle grammaire et au modèle par expression régulière.
- Savoir démontrer qu’un langage n’est pas rationnel.
- Savoir identifier les langages algébrique et distinguer les langagés algébrique déterministe des langages algébrique non déterministe.
- Savoir mettre une grammaire algébrique sous forme normale de Chomsky et concevoir l'automate à pile correspondant.
Plan du cours
Résumé du cours :
Alphabets, Mots, Langages, Langages réguliers, Expressions regulières, Automates finis déterministe (AFD), Automates finis non déterministe (AFN), Minimisation d’un AFD, Equivalence entre AFD, AFN et expressions régulières, Lemme de l’étoile ou de pompe.
CM1/CM2/CM3 -> Langages formels: Langage, manipulation des concepts de langages, de définitions de langages, de fermeture de Kleene...
CM4/CM5 -> Automates à états fini AFD, AFN, AFN-e, mise en oeuvre des procédés algorithmiques de minimisation et de déterminisation d'AEF.
CM6/CM7/CM8 -> Langages rationnels : Langages rationnels, Opérations rationnelles, Expressions rationnelles, Grammaires linéaires à droite ou à gauche, Lemme de l'étoile.
CM9/CM10 -> Langages algébriques: Automates à piles et lemme de l'étoile.
Description des TP
TD1: Langage, manipulation des concepts de langages, définitions de langages, de fermeture de Kleen...
TD2: Grammaires, conception de grammaires engendrant un langage donné.
TD3: Langages ratonniels, conception d'automates, de grammaires ou d'expressions régulières définissant un langage rationnel donné.
TD4: Automate à Etats Fini (AEF), mise en oeuvre des procédés algorithmiques de minimisation et de déterminisation d'un AEF.
TD5: Equivalence de modèles, mise en oeuvre de transformation de modèles de description d'un langage rationnel.
TD6: Frontière des langages rationnels, démontrer qu’un langage est non rationnel en appliquant la contraposée de lemme de la pompe.
Connaissances requises
Pas de pré requis
RSE (Responsabilité Sociale et Environnementale)
Bibliographie
-
[HMU] Introduction to Automata Theory, Langage and Computation J.E. Hopcroft, R. Motwani, J.D. Ullman Edition Adison Wesley 2001;
-
[DPPA10] Logicomix, A. Doxiadis, C. Papadimitriou, A. Papadatos, A.D. Donna Edi. Vuibert 2010;