/
Français
English
No description
UE Automates et langages
ECUE's code : SLUIN501
PORTAIL SCIENCES ET TECHNOLOGIES
Informatique
Campus Valrose
Licence 3
Semestre impair
Français
PRESENTATION
Ce cours présente la théorie classique des automates et des langages formels. Il s'appuie sur la hiérarchie de Chomsky pour les langages et présente successivement les langages réguliers, les expressions régulières, les automates finis, les grammaires régulières et le théorème de Kleene. Les algorithmes de déterminisation, minimisation et de passage d'un modèle à un autre ainsi que les propriétés de clôture y sont décrits en détail. Les démonstrations se font le plus souvent par construction, par induction ou de façon algorithmique. Des grammaires régulières le cours passe aux grammaires hors-contexte, aux langages hors-contexte et aux automates à pile. Là encore, les relations entre les différents modèles et les propriétés de clôture sont étudiées.
Le cours se poursuit avec les formes spéciales des grammaires et le problème de l'appartenance, ainsi que les algorithmes correspondant, en particulier, celui de Cocke Youger et Kasami. Le cours se termine sur l'étude des machines de Turing et une brève
évocation de la théorie de la calculabilité avec la notion de procédure effective et la thèse de Church-Turing.
Les TP concernent plusieurs applications empruntées aux domaines de la reconnaissance de motifs, de la compression, de la spécification des langages de programmation ou de la distance d'édition.
Course's manager(s)
Sandrine Julia
In class
- 18h of lectures
- 24h of directed studies
- 12h of practical work
PREREQUISITES
Before the start of the course, I must ...
-
Avoir suivi un cours de programmation et idéalement le cours d'Outils Formels pour l'Informatique de L2.
OBJECTIVES
By the end of this course, I should be able to...
- Comprendre ce fondement théorique de l'informatique que constitue la théorie des machines, des langages formels et aussi en connaître les principales applications.
CONTENT
-
Langages rationnels (ou réguliers)
-
Automates finis
No description
-
Expressions régulières
No description
-
Grammaires régulières
No description
-
Grammaires hors-contexte (ou algébriques)
No description
-
Automates à pile
No description
-
Langages hors-contexte (ou algébriques)
No description
-
Grammaires contextuelles
No description
-
Machines de Turing
No description
-
Automates cellulaires
No description
Access to complete Syllabus (Authentification required)
Important
This syllabus has no contractual value. Its content is subject to change throughout this year: be aware to the last updates