Langages rationnels

Plan détaillé

Mots
- alphabet, lettre, mot, longueur d'un mot, notation |u|, mot vide, notation A^*
- concaténation de deux mots, monoïde, semigroupe
Opération rationnelles
- langages
- exemples L = { u | |u| pair } et L' = { u | |u| impair }
- union, produit, étoile
- exemples LL, LL', L'L', { a, ba }^*
- expression rationnelle
- exemples A*, aA^*, (aa+b)^*, (ab^*a+b)^*
Automates finis
- definition A = (Q, A, E, I, F)
- exemple A = ({0, 1}, {a, b}, {(0,a,1), (0,b,0), (1,a,0), (1,b,1)}, {0}, {0})
- chemin, chemin acceptant, mot accepté, langage accepté
- théorème de Kleene
  - automates normalisés
  - passage d'une expression à un automate
  - algorithme de McNaugthon-Yamada
  - élimination d'états sur l'exemple précédent
  - résolution d'un système sur l'exemple précédent
- automates déterministes
- déterminisation
- exemple A = ({0, 1, 2}, {a, b}, {(0,a,0), (0,b,0), (0,a,1), (1,b,2), (2,a,2), (2,b,2)}, {0}, {2})
- complétion d'un automate
- complémentation
- exemple de A^*abA^*

Minimisation (cf. [BBC03])
- automates des quotients
- morphismes d'automates
- congruences de Nerode
  - calcul par raffinement successifs
  - algorithme de Hopcroft
Critères de rationalité (cf. [Sak03] p. 77 et p. 127)
- lemmes de l'étoile
- nombre fini de quotients
Propriétés de clôture des langages rationnels
- opérations booléennes : union, intersection et complémentation
- quotient par un mot ou un langage
- image inverse ou directe par morphisme et substitution
- mirroir, décimation

Pour cette partie, consulter [Pin86] pour un exposé complet et [Per90]) pour une preuve élémentaire du théorème de Schützenberger.