Théorie des langages 2

Ce cours du semestre 4 est la suite directe de « Théorie des langages » du semestre 3, consacré aux langages réguliers et aux automates finis. Il monte dans la hiérarchie de Chomsky : langages algébriques et automates à pile, qui modélisent l’analyse syntaxique des programmes et des formats structurés, puis machines de Turing, qui définissent la notion même d’algorithme, et enfin les limites du calcul (langages décidables et semi-décidables, problème de l’arrêt, théorème de Rice). Pour un futur professionnel de la cybersécurité, ces résultats expliquent pourquoi les analyseurs d’entrées doivent être stricts et bornés, et pourquoi aucun antivirus ne peut détecter parfaitement tous les programmes malveillants.

Objectifs d’apprentissage

• Manipuler les grammaires algébriques : arbres de dérivation, ambiguïté, simplification, forme normale de Chomsky.
• Décider l’appartenance d’un mot avec l’algorithme CYK.
• Construire et faire fonctionner des automates à pile ; passer d’une grammaire à un automate à pile.
• Prouver qu’un langage n’est pas algébrique avec le lemme de pompage.
• Construire et tracer des machines de Turing simples ; expliquer la thèse de Church-Turing.
• Distinguer décidable et semi-décidable, prouver une indécidabilité par réduction et en tirer les conséquences en sécurité.

Prérequis

Théorie des langages S3 (mots, langages, grammaires, hiérarchie de Chomsky, automates finis, expressions régulières, lemme de l’étoile) ; raisonnement par récurrence et par l’absurde.

Plan du cours

1. Grammaires algébriques : arbres, ambiguïté, formes normales et CYK
2. Automates à pile et propriétés des langages algébriques
3. Machines de Turing et thèse de Church-Turing
4. Langages décidables, semi-décidables et problème de l’arrêt

Modalités d’évaluation

Volume horaire : 13 h de cours magistral, 7 h de travaux dirigés, 20 h de travail personnel (2 crédits). Évaluation : contrôle continu (quiz en ligne, exercices de TD : conversions en FNC, tables CYK, traces d’automates à pile et de machines de Turing) et examen terminal écrit.

Bibliographie

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson (Addison-Wesley).
• Michael Sipser, Introduction to the Theory of Computation, Cengage Learning.
• Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008.
• Pierre Wolper, Introduction à la calculabilité, Dunod.
• Alan M. Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, 1936.