Langages formels, calculabilité et complexité à l'ENS en 2005/2006

Cours n° 1 (jeudi 29 septembre) : automates et langages rationnels
- 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
  - définition 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^*
Cours n° 2 (jeudi 6 octobre) : minimisation d'automates
- 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
Cours n° 3 (jeudi 13 octobre) : approche algébrique
- Reconnaissance par morphisme
  - monoïde, sous-monoïde, morphisme, quotient, division
  - reconnaissance par morphisme
  - équivalence entre automates et monoïdes finis
  - monoïde syntaxique
  - calcul du monoïde syntaxique sur l'automate minimal
- Langages sans étoile
  - définition
  - exemples (ab)^*, (ab+ba)^*
  - théorème de Schützenberger
  - exposant d'un semigroupe
  - monoïdes apériodiques
- Cours n° 4 (jeudi 20 octobre) : grammaires et langages algébriques
  - Grammaires
    - définition et exemples
    - grammaires réduites
    - grammaire propres
    - système d'équations associé à une grammaire
    - arbres de dérivation
    - ambiguïté
    - forme normale quadratique
  - Lemmes d'itérations
    - lemmes d'Ogden
    - application à L = { aⁿbⁿcⁿ | n ≥ 0 }
    - application à l'ambiguïté de L = { aⁿbⁿc^* | n ≥ 0 } ∪ { a^*bⁿcⁿ | n ≥ 0 }
- Cours n° 5 (jeudi 27 octobre) : automates à pile
  - Propriétés de clôture des langages algébriques
    - opérations rationnelles
    - grammaires linéaires droites (gauches)
    - substitution algébrique
    - morphisme alphabétique inverse
    - intersection avec un rationnel
    - théorème de Chomsky-Schützenberger
  - Forme normale de Greibach
  - Automates à pile
    - définitions et exemple
    - différents modes d'acceptation
    - équivalence avec les grammaires
  - Automates déterministes
- Cours n° 6 (jeudi 3 novembre) : Calculabilité I
- Cours n° 7 (jeudi 10 novembre) : Calculabilité II
- Cours n° 8 (jeudi 17 novembre) : Calculabilité III
- Cours n° 9 (jeudi 1^er décembre) : Complexité I
- Cours n° 10 (jeudi 8 décembre) : Complexité I
- Cours n° 11 (jeudi 15 décembre) : Compléments I
- Cours n° 12 (jeudi 5 janvier) : Compléments II