Différences

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

--- formations:licence:ue:l2:aal3 [2025/01/29 10:45] – ↷ Page déplacée de formations:licence:ue:l2:aal3 à formations:licence:2024-2025:ue:l2:aal3 admin
+++ 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 pour utilisateurs

Outils du site

Différences

Outils de la page