UFR Informatique

Outils pour utilisateurs

Outils du site

Vous êtes ici : Accueil » formations » licence » ue » l2 » aal3
formations:licence:ue:l2:aal3

Différences

Ci-dessous, les différences entre deux révisions de la page.


Révision précédente
—formations:licence:ue:l2:aal3 [2025/01/29 10:50] (Version actuelle) – ↷ Page déplacée de playground:formations:licences:ue:l2:aal3 à formations:licence:ue:l2:aal3 admin
Ligne 1: Ligne 1:
 +~~NOTOC~~
 +====== Automates et Analyse Lexicale (AAL3) ======
  
 +===== Description =====
 +
 +Ce cours est une introduction à la théorie des automates finis et des langages formels, ainsi qu'à l'analyse lexicale.
 +
 +Les langages rationnels sont étudiés tant sous l'angle algorithmique qu'algébrique. Sont abordés en particulier des algorithmes pour transformer une expression rationnelle en automates et vice-versa, pour déterminiser un automate et le minimiser ; mais aussi le lemme d'itération ou la caractérisation de Myhill-Nerode des langages rationnels selon leur nombre de résiduels.
 +
 +Enfin, l'introduction à l'analyse lexicale est une application des techniques enseignées dans ce cours à la construction des compilateurs. 
 +
 +===== Syllabus =====
 +
 +==== Sujets centraux ====
 +
 +  - Langages et opérations sur les langages
 +  - Expressions rationnelles
 +  - Automates déterministes
 +  - Automates non-déterministes, et déterminisation
 +  - Automates avec transitions "epsilon", et élimination des transitions "epsilon"
 +  - Algorithme de Thompson pour la transformation d'une expression rationnelle en automate
 +  - Algorithme de Glushkov pour la transformation d'une expression rationnelle en automate
 +  - Automates généralises, et algorithme de Brzozowksi-McCluskey pour la transformation d'un automate en expression rationnelle
 +  - Équivalence entre expression rationnelles et automates, propriétés de clôture de la classe des langages reconnaissables
 +  - Analyse lexicale : principe, et utilisation d'un générateur du type //lex//
 +  - Le lemme d'itération, et son utilisation pour montrer qu'un langage n'est pas reconnaissable
 +  - Calcul du résiduel d'une expression rationnelle par rapport à une lettre, et construction de l'automate des résiduels pour une expression rationnelle
 +  - Le théorème de Myhill-Nerode, et utilisation des résiduels pour montrer qu'un langage n'est pas reconnaissable
 +  - Minimisation d'automates déterministes par la méthode de Moore
 +
 +==== Sujets potentiellement traités ====
 +  - Le lemme d'Arden, et son utilisation pour transformer un automate en expression rationnelle
 +  - Aspects avancés de //lex// : utilisation d'états multiples, utilisation d'une table de hachage
 +  - Minimisation d'automates déterministes par la méthode de Brzozoswki
 +  - Automates bi-directionnels
 +  
 +===== Pré-requis =====
 +
 +Programmation en Java, les bases de la programmation orientée objet inclus, par exemple comme enseigné dans le cours [[..:l1:ip2|Initiation à la programmation 2]].

Outils de la page

Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki