University Côte d'azur
/ Formation / Syllabus SLUIN501
Français English

UE Automates et langages

ECUE's code : SLUIN501

Belong to 0 UE
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

  • No description
  • No description
  • No description
  • No description
  • No description
  • No description
  • No description
  • No description
  • No description
  • 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