Théorie
des langages et des automates
Année universitaire 2020/2021
Préambule
● Initiation à la théorie des langages formels.
● Les langues sont les supports de communication.
● Les langues permettent aux hommes d'échanger entre eux des
informations et des idées.
● Les langages leur permettent de communiquer avec les machines. ●
Les langues utilisées dans la vie de tous les jours entre êtres humains
sont dites naturelles. Elles sont généralement informelles et ambigües
et demandent toute la subtilité d'un cerveau humain pour être
interprétées correctement.
● Les langages formels créés par l'homme pour communiquer avec les
ordinateurs sont non ambigus pour pouvoir être interprétés par une
machine.
2
1
Préambule
●À la base, un ordinateur ne comprend qu'un seul langage, pour lequel
il a été conçu: son langage machine.
● Pour communiquer avec des langages plus évolués, il est nécessaire
d'utiliser un interprète (qui traduit interactivement les instructions
entrées au clavier), ou bien un compilateur (qui traduit tout un
programme).
Plan du cours
Chapitre Remarques sur le contenu du chapitre Charg TD Charg
e e
horair horair
Chapitre 1 : ∙ Introduction générale e TD1: e
Introduction: ∙ Préambule et motivations Expressions TD
mots et ∙ Mots et langages --- et Langages ---
langages Réguliers
Chapitre 2 : ∙ Les expressions régulières --- TD1: ---
Automates finis et ∙ Les automates finis non déterministes Expressions
Expressions ∙ Les automates finis déterministes et Langages
régulières ∙ Les automates avec ε-transitions Réguliers+
∙ Les automates minimals TD2:
Automates à
états finis
Chapitre 3 : ∙ Les grammaires ---- TD3 : ----
Les grammaires ∙ Langage engendré par une grammaire Grammaires
∙ Types de grammaires et Automates
∙ grammaires et dérivation à piles
∙ Transformation d'une grammaire régulière en un
automate fini
∙ Transformation d’automate fini en une grammaire
régulière
Chapitre 4 : ∙ Généralités. ---- TD3 : ----
Automate à piles ∙ Configurations. Grammaires
∙ Exemple introductif. et Automates
∙ Automates à pile et automates traditionnels. à piles
∙ Transitions dans un PDA
∙ Langage reconnu par un PDA
Chapitre 5 : ∙ Généralités --- Exercices ----
Machine de Turing ∙ Fonctionnement d’une Machine de Turing d’application
∙ TM pour langages réguliers
∙ TM pour les langages hors contexte
2
Plan du cours
Chapitre Remarques sur le contenu du chapitre Char TD Charg
ge e
horai horair
Chapitre 1 : ∙ Généralités re TD1: Analyse e
Analyse Lexicale ∙ Unité lexicale, Lexème et Modèles Lexicale TD
--- TP1: Flex ---
(Introduction)
Chapitre 2 : ∙ Rôle de l’analyseur syntaxique --- TD2: Analyse ---
Analyse Syntaxique ∙ Suppression de la récursivité à gauche Syntaxique
∙ Factorisation à gauche TP2: Bison
∙ Analyse syntaxique Descendante
∙ Analyse syntaxique Ascendante
Chapitre 3 : ∙ Rôle et phases de l’analyse sémantique ---- TD3 : Analyse ----
Analyse Sémantique ∙ Outils pour effectuer l’analyse sémantique ∙ Sémantique
Représentation et reconnaissance des types
∙ Dictionnaires (tables de symboles)
Chapitre 4 : ∙ Généralités. ---- TD4 : ----
Production de code ∙ Les objets et leurs adresses Génération
∙ Code intermédiaire de code
∙ Architecture du processeur
évaluation
● Une note de contrôle continu
● Une note sur le devoir surveillé
● Une note sur l’examen
Note CC + Note DS 🡺 40% de la note Finale
Note Examen 🡺 60% de la note Finale
Moyenne = Contrôle Continu * 40% + Examen * 60%
3
Motivations
● Description
et analyse de langages (traitement du texte, codes,
langages de programmation, langages naturels, . . . )
● Modèles de calcul, conception d’algorithmes.
Bibliographie
● [Link], J.D. Ullman. Introduction to automata theory, languages
and computation. Addison-Wesley, 1979.
● M. Sipser. Introduction to the theory of computation. PWS Publishing
Company, 1996.
● A. Lingas, R. Karlsson, S. Carlsson. Automata, Languages and
Programming. Lecture Notes in Computer Science – 20th
International Colluquium ICALP93. Springer-Verlag Ed.
