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