Documents#
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