Introduction au module

Version : 2.71

Présentation du cours

Le module "Langages formels" vise à introduire les bases de la théorie des langages, des automates ainsi que les principales notions sur lescompilateurs. Il permet d'appréhender un certain nombre de techniquesfondamentales :

• de nouvelles techniques de programmation (notion de programmation dirigée par la syntaxe)
• le contrôle de validité
• la compréhension et optimisation de nouveaux outils proposant l'utilisation des expressions régulières (Perl, PHP, JDK 1.4...)
• la présentation de bases pour des techniques de CSI (modélisation dynamique en UML) et de compilation (analyseurs lexicaux).
• ...

Ce cours propose aussi d'habituer l'étudiant à des formalisations et démonstrations utiles pour d'autres cours.

Nous y définissons les notions suivantes : vocabulaire, langage, grammaires, classification de Chomsky, langages relationnels, expressions régulières, machine de Turing, automates déterministes et non-déterministes. Nous présentons aussi bien les bases théoriques nécessaires à la bonne compréhension de ces notions que des algorithmes de base permettant de les manipuler. En particulier,nous nous attachons à présenter les outils permettant de construire un analyseur de chaînes de symboles à partir d'une ou plusieurs expressions décrivant leur construction (le langage). 

Prérequis

Pour comprendre les notions abodées dans ce modules, il est nécessaire de bien maitriser les concepts suivants : théorie des ensembles, démonstration par l'absurde et démonstration par induction, algorithmique, programmation impérative (éventuellement programmation objet Java).

Du point de vue de l'e-miage, les modules suivants sont conseillés pour bien aborder le module B209 :

• A101 : Mathématiques générales
• A102 : Mathématiques pour l'informatique
• B104 : Théorie des graphes et combinatoire
• A204 : Programmation impérative et algorithmique
• A205 : Algorithmique et structures de données

Plan de ce cours

Nous débuterons ce cours par une présentation des bases de la théorie des langages formels (Chap. 2). Nous présenterons les notions de base : alphabet, chaîne, mot, langage... ainsi que les opérations associées sur les mots et les langages. Nous insisterons notamment sur une classe de langage particulière : les langages rationnels (Chap. 3). Nous donnerons des définitions et des outils permettant de les décrire dont principalement les expressions régulières. Nous présenterons aussi une méthode permettant de déterminer si un langage n'est pas rationnel, basée sur le lemme de la pompe.

Nous introduirons aussi les grammaires (Chap. 4) permettant de définir un langage. Une grammaire (ou syntaxe) est un ensemble de règles applicables à un vocabulaire définissant les phrases bien formées du langage. Cette analyse se situe à un niveau purement syntaxique. Une phrase appartenant à un langage peu ne pas avoir de sens d'un point de vue sémantique mais en avoir du point de vue syntaxique. Une grammaire a deux fonctions : produire (des phrases syntaxiquement correctes) et reconnaître (des phrases comme syntaxiquement correctes).

Ensuite, nous introduirons rapidement les machines de Turing avant de nous attarder sur un cas particulier : les automates à nombre fini d'états (Chap. 5) (appelé aussi Automates d'états finis ou automate fini). Nous donnerons toutes les définitions nécessaires à leur compréhension et à leur utilisation. De plus, nous verrons comment les "optimiser" en les rendant déterministes et minimaux. Nous proposerons aussi une succession d'algorithmes permettant de combiner et transformer ces automates finis.

Après avoir montré l'équivalence entre les langages rationnels et les langages reconnus par les automates finis (Chap. 6) (théorème de Kleene), nous présenterons aussi des méthodes permettant de passer d'une expression régulière (décrivant un langage rationnel) à un automate fini déterministe et minimal capable de reconnaître des mots de ce langage ainsi que les opérations inverses.

Enfin, nous exposerons des applications (Chap. 7) possibles des automates finis. Nous verrons en particulier leur utilisation dans le processus de compilation d'un langage informatique et dans le traitement du langage naturel.

Certaines parties sont relativement indépendantes et peuvent donc être abordées en parallèle. Le graphe ci-dessous présente les dépendances entre les grandes parties de ce cours. Les icônes indiquent les devoirs à effectuer.

Participants

Responsable du module :

• Emmanuel Desmontils (MIAGE de Nantes)

Remerciement :

• à Sophie Coudert pour sa participation à la rédaction du polycopié du module "Automates" en seconde année de la MIAGE durant l'année 1998-1999, polycopié qui a servi de base à ce cours.
• à Bengamin Habegger pour sa participation aux TD et TP entre 2000 et 2004 et ses remarques sur les sujets de TD et TP qui sont la base des exercices de ce cours.
• à Alain Vailly et Annie Tartier pour leurs conseils et leur soutien.

Notations

Il y a peu de conventions spécifiques pour ce cours. Cependant, nous essayerons de respecter les notations suivantes :

et un texte	indique une définition.
et un texte	indique un théorème, parfois suivi d'une démonstration
et un texte	indique un lemme, parfois suivi d'une démonstration
	indique une remarque importante.
Exercices et tests	indique une série d'exercices pour tester les connaissances acquises
ou	indiquent une aide pour résoudre un exercice
	indique la solution à un exercice

Bibliographie

Les références en gras sont celles qui ont été plus particulièrement utilisées pour la construction de ce cours.

• A. Aho, R. Sethi & J. Ullman, "Compilateurs : principes, techniques et outils", InterEditions, 1991.
• P. André, A. Vailly, "Conception des systèmes d'information : Panorama des méthodes et des techniques", série Technosup, Ed. Ellipses, Paris, 2001, ISBN 2-7298-0479-X.
• J.-M. Autebert, "Théorie des langages et des automates", Masson, 1994.
• N. Chomsky, "Three models for the description of language", In Proc. of the Symposium on Information Theory, ED. IRE Trans. Inf. Th., IT-2, 1956
• Patrick Bellot & Jacques Sakarovitch, "Logique et automates", série Manuel d'Informatique, Ed. Ellipses, Paris, 1998, ISBN 2-7298-6894-1
• J. E. F. Friedl, "Maitrise des Expressions Régulières", O'Reilly, 2002
• A. Ginzburg, "Algebraic Theory of Automata", ACM, Academic Press, 1968
• S. C. Kleene, "Representation of events in nerve nets and finite automata", In Automata Studies, C. E. Shannon & J. McCarthy Eds, Princeton University Press, 1956, pp. 3-42.
• M. Lucas, J.-P. Peyrin & P.-C. Scholl, "Algorithmique et représentation des données : 1 - Files, automates d'états finis", Masson, 1983
• P. Linz, "Formal Languages and Automata", Jones and Barnett Publishers, 2006
• T. Niemann, "A Guide to LEX & YACC" http://www.informatik.hu-berlin.de/~mueller/codeopt/y_man.pdf (lien devenu invalide)
• D. Perrin, "Les débuts de la théorie des automates", TSI, 14:409-443, 1995 www-igm.univ-mlv.fr/~perrin/Recherche/Publications/Loi/copie3.ps
• Charles Platt, "What's It Mean to Be Human, Anyway?", >http://www.usyd.edu.au/su/social/papers/platt.html (lien devenu invalide)
• Patrice Séébold, "Théorie de automates : méthodes et exercices corrigés", série Passeport pour l'informatique, Ed. Vuibert, Paris, 1999, ISBN 2-7117-8630-7, www.vuibert.fr
• K. Thompson, "Regular expression search algorithm", Communication of the ACM, 11(6):419-422, 1968
• A. Turing, "On computable numbers with an application to the entscheidungs problem". Proceedings of the London Math. Soc., 42:230-265, 1936
• P. Verdret, "De Perl à Java : programmation des expressions régulières", Hermès, 2005
• B. W. Watson, "A taxonomy of finite automata construction", Computing Science Note 93/43, Eindhoven University of Technology, The Netherlands, 1993 ftp://ftp.win.tue.nl/pub/techreports/pi/automata/taxonomy/2nd.edition/constax.ps.Z
• B. W. Watson, "A taxonomy of finite automata minimization algorithms", Computing Science Note 93/44, Eindhoven University of Technology, The Netherlands, 1993 ftp://ftp.win.tue.nl/pub/techreports/pi/automata/taxonomy/2nd.edition/mintax.ps.Z
• R. Wilhelm & D. Maurer, "Les compilateurs : théorie, construction, génération", Masson, 1994

Cours Web

• G. Coray, "Automates et Calculabilité II",Semestre d'été - 2003, http://lithwww.epfl.ch/teaching/tac/ (lien devenu invalide)
• G. Falquet, "Outils formels pour les systèmes d'information (hiver 00-01)", http://cui.unige.ch/isi/ofsi00/
• A. Felty,"CSI 3504 Introduction aux langages formels", Hiver 2003, http://www.site.uottawa.ca/~afelty/courses/csi3504/ (lien devenu invalide)
• S. Gire, " COMPILATION - THÉORIE DES LANGAGES", http://fastnet.univ-brest.fr/~gire/COURS/COMPIL_IUP/POLY.html
• S. Julia, "Automates & Langages", http://deptinfo.unice.fr/%7ejulia/L1/ (lien devenu invalide)
• L. Lander, "CS573 : Automata Theory and Formal Languages", Thomas J. School of Engineering and Applied Science, Binghamton University, University of New York, 1998 http://bingweb.binghamton.edu/~lander/cs573.html (lien devenu invalide)
• David Matuszek, "Theory of Computation", http://www.netaxs.com/people/nerp/automata/syllabus.html (lien devenu invalide)
• M. Pichat & C. Solnon, "Théorie des Langages", http://www710.univ-lyon1.fr/~csolnon/langages.html
• H. Shapiro, "CS500: Introduction to the Theory of Computation", The University of New Mexico, 1997 ftp://ftp.cs.unm.edu/pub/shapiro/CS500/chapter3.ps (lien devenu invalide)
• A. Tisseran, "QUELQUES ELEMENTS DE THEORIE DES LANGAGES", http://www.mines.u-nancy.fr/~tisseran/cours/langages/
• Turing's World, http://www-csli.stanford.edu/hp/Turing1.html
• Langages et compilation, Cyril Banderier, Paris XIII, Mai 1999, http://www-lipn.univ-paris13.fr/~banderier/P13/html/
• ... Et il y en a bien d'autres !

Plus généralement, des bases de cours : http://rangiroa.essi.fr/cours/ & http://rangiroa.essi.fr/specif/spedago/index.html

Outils

• JFLAP, Susan H. Rodger, http://www.jflap.org/
  Cet outil sera régulièrement utilisé pour illustrer cours et exercices.
• Eileen Head, http://www.cs.binghamton.edu/~software/