Regular Expressions and Closure Properties


Documents

  1. Expression régulières (handouts)  

  2. Minimisation des DFA (handouts)  

  3. Résumé de cours (M. Pantel)  

Compétences travaillées

  • exprimer le language d'un automate sous forme de regex (utilisation du lemme d'Arden et simplification d'états)
  • construire un automate qui reconnaît le même language qu'une regex
  • propriétés de clôture sur les automates; construction de Thompson
  • résiduels d'un langage et dérivées d'une regex; construction de Brzozowski
  • définition de la classe des langages rationels; théorème de Myhill-Nerode
  • équivalence entre ces différentes définitions (théorème de Kleene)
  • quelques notions sur les algorithmes de string matching
  • DFA minimal et algorithme de minimisation