UE Automates et langages

Code de l'ECUE : SLUIN501

Ce cours donne droit à 6.0 ECTS.

Structure

PORTAIL SCIENCES ET TECHNOLOGIES

Domaine disciplinaire

Informatique

Lieu d'enseignement

Campus Valrose

Niveau du cours

Licence 3

Semestre

Semestre impair

Langue

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.

Responsable(s) du cours

Sandrine Julia

Présentiel

18h de cours magistral
24h de travaux dirigés
12h de travaux pratiques

PREREQUIS

Avant le début du cours, je dois ...

Avoir suivi un cours de programmation et idéalement le cours d'Outils Formels pour l'Informatique de L2.

OBJECTIFS

A la fin de ce cours, je devrais être capable de...

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.

CONTENU

Langages rationnels (ou réguliers)

Aucune description
Automates finis

Aucune description
Expressions régulières

Aucune description
Grammaires régulières

Aucune description
Grammaires hors-contexte (ou algébriques)

Aucune description
Automates à pile

Aucune description
Langages hors-contexte (ou algébriques)

Aucune description
Grammaires contextuelles

Aucune description
Machines de Turing

Aucune description
Automates cellulaires

Aucune description

Accéder au Syllabus complet (Authentification requise)

Important

Ce syllabus n’a aucune valeur contractuelle. Son contenu est susceptible d’évoluer en cours d’année : soyez attentifs aux dernières modifications.