La théorie des langages
Ce livre est une introduction aux langages formels, qui constituent un des fondements de la science informatique. Il existe d’excellents ouvrages en anglais traitant de ce sujet, mais très peu en français, conciliant à la fois, le cours, les exercices, et leurs solutions. Celui-ci tente humblement de donner les éléments nécessaires aux lecteurs intéressés dans le domaine, tout en proposant à la fin de chaque chapitre une série d’exercices avec leurs corrigés. Aussi, il couvre la totalité des programmes des étudiants informaticiens en ingéniorat et en LMD. Il s’adresse également aux étudiants en mathématiques discrètes. La théorie des langages est à l’origine de différents domaines d’applications, tels que la compilation des langages de programmation évolués, la modélisation dans la vérification et la validation des systèmes physiques. Par le mot ‘formel’, on comprend que le concept est exprimé dans un langage mathématique, ou dans un formalisme rigoureusement défini, en faisant abstraction de son sens, c'est-à-dire en ne tenant compte que de son aspect syntaxique. Le premier chapitre traite des rappels mathématiques, utilisés dans la suite du cours. Le deuxième chapitre présente les concepts fondamentaux de la théorie des langages formels, ainsi que des notions de la combinatoire des mots. Dans le troisième chapitre sont introduits les systèmes de réécriture, avec comme corollaire les grammaires formelles, ainsi que la typologie des grammaires telle qu’elle est définie par Noam Chomsky. Le quatrième chapitre étudie la classe des langages réguliers, qui est la plus petite classe, au sens de l’inclusion des langages. Ce chapitre a pour objet l’étude des différentes formes d’automates d’états finis, appelés aussi automates de Rabin-Scott. Il montre l’équivalence entre les automates de Rabin-Scott et les grammaires régulières à droite pour montrer que la classe des langages réguliers est égale à la classe des langages acceptés par les automates d’états finis. Il est à noter que les automates de Rabin-Scott sont très utilisés dans la partie analyse lexicale d’un compilateur, et dans la modélisation pour la validation et la vérification de propriétés des systèmes physiques réels. Ce chapitre est clôturé par l’étude des propriétés de fermeture de la classe des langages réguliers. Le but du cinquième chapitre est de présenter le concept d’expression régulière, afin de montrer son équivalence avec l’automate de Rabin –Scott et donc aussi avec les grammaires régulières à droite. Le sixième chapitre est consacré aux langages à contexte libre. Il est fondamental pour les bases de la compilation, notamment dans sa partie analyse syntaxique, puisque c’est dans ce chapitre que l’automate à pile est présenté. L’automate à pile est une extension de l’automate de Rabin-Scott, et il est utilisé dans la plupart des méthodes d’analyse syntaxique en compilation. Ce chapitre consacre également une bonne partie pour la transformation des grammaires à contexte libre pour les préparer à l’analyse syntaxique. Le septième chapitre porte sur les langages à contexte lié, où l’automate à bornes linéaires, qui constitue un cas particulier de la machine de Turing, est présenté. Le huitième et dernier chapitre introduit des notions de calculabilité en définissant la machine de Turing et le problème de Post.
Livres dans la même catégorie
Avis des lecteurs
Aucun avis pour le moment.