~~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]].