Langages formels, calculabilité et complexité à l'ENS en 2006/2007
- Cours n° 1 (jeudi 28 septembre) : combinatoire et automates
- Mots
- alphabet, lettre, mot, longueur d'un mot, notation |u|, mot vide,
notation A*
- concaténation de deux mots, monoïde libre
- morphisme de monoïdes libres
- 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)*
- Combinatoire des mots
- Périodicités
- théorème de Fine et Wilf
- mots de Fibonacci
- énoncé du théorème de Guibas et Odlyzko
- Bon quasi-ordres
- équivalences des différentes définitions
- théorème de Higman
- Mots sans carrés
- définition d'un carré et d'un chevauchement
- morphisme de Thue-Morse
- mots sans chevauchement
- mots sans carré
- 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 pour le passage d'une expression
à un automate
- Cours n° 2 (jeudi 5 octobre) : minimisation d'automates
- théorème de Kleene (suite)
- 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*abaA*
- Minimisation (cf. [BBC03])
- automates des quotients
- congruence d'automates
- congruences de Nerode
- calcul par raffinement successifs
- algorithme de Hopcroft
- Cours n° 3 (jeudi 12 octobre) : approche algébrique
- lemmes de l'étoile et ses variantes
- 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 (sans preuve)
Cours n° 4 (jeudi 19 octobre) : Grammaires
- Grammaires
- définition et exemples
- grammaires linéaires droites (gauches)
- grammaires réduites
- grammaire propres
- système d'équations associé à une grammaire
- théorème de Parikh
- arbres de dérivation
- ambiguïté
- forme normale quadratique
- Lemmes d'itérations
- lemmes d'Ogden
- application à L =
{ anbncn | n ≥ 0 }
- application à l'ambiguïté de L =
{ anbnc* | n ≥ 0 } ∪
{ a*bncn | n ≥ 0 }
Cours n° 5 (jeudi 2 novembre) : Automates à piles
- Propriétés de clôture des langages algébriques
- opérations rationnelles
- 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 16 novembre) : semi-décidabilité
- Machines de Turing
- notion de problème et de codage
- définition et exemples
- normalisation
- composition
- fonction calculée par une machine de Turing
- machines à bande bi-infinie
- machines à plusieurs bandes
- machines non déterministes/machines déterministes
- Langages récursivement énumérables
- définition
- équivalence avec les énumérateurs
- propriétés des langages récursivement énumérables
- exemple de langage non récursivement énumérable
par argument diagonal
Cours n° 7 (jeudi 23 novembre) : décidabilité
- Langages décidables
- définition
- machine universelle
- propriétés des langages récursivement énumérables
- exemple de langage récursivement énumérable
mais pas décidable
- Réductions
- définition
- réduction du problème d'acceptation au problème de l'arrêt
- réduction du problème d'acceptation au problème du vide
- réduction du problème du vide au problème de l'égalité
- Problème de correspondance de Post (PCP)
- définitions de PCP et de PCP Modifié (PCPM)
- équivalence entre PCP et PCPM
- réduction du problème d'acceptation à PCP
- application aux grammaires algébriques
- indécidabilité de LG(S) ∩ LG'(S')
= ∅
- indécidabilité de LG(S) = A*
- indécidabilité de LG(S) = LG'(S')
- indécidabilité de l'ambiguïté d'une grammaire
Cours n° 8 (jeudi 30 novembre) : compléments
- Théorème de récursion
- programme qui s'écrit
- programme qui manipule son propre source
- application à l'indécidabilité de l'acceptation
- point fixe de transformations de programmes
- Décidabilité de théories logiques
- décidabilité de ⟨N, +⟩
- indécidabilité de ⟨N, +, x⟩
- Écriture des entiers dans une base
Cours n° 9 (jeudi 7 décembre) : complexité en temps
- Complexité en temps et en espace
- complexité en temps et en espace d'une machine
- théorème d'accélération
- changements de modèles
- classes de complexité en temps
- Temps polynomial
- exemples de problèmes en temps polynomial déterministe
- accessibilité dans un graphe
- langages algébriques
- exemples de problèmes en temps polynomial non déterministe
- chemin hamiltonien
- satisfiabilité d'une formule
- Réductions polynomiales
- NP-complétude
- définition de NP-difficile et NP-complet
- NP-complétude de SAT et 3SAT
- Exemples de problèmes NP-complets
- couverture de sommets
- chemin hamiltonien
- problème de la somme
Cours n° 10 (jeudi 14 novembre) : complexité en espace
- Complexité en espace
- liens entre la complexité en temps et en espace
- classes de complexité en espace
- théorème de Savitch
- Espace polynomial
- exemples de problèmes en espace polynomial
- L(M) = A* pour un automate non déterministe M
- relations entre les classes P, NP, PSPACE et EXPTIME.
- PSPACE-complétude
- définition
- PSPACE-complétude de la vérité des formules booléennes quantifiées
Cours n° 11 (jeudi 21 décembre) : Compléments I
- théorèmes de hiérarchie
- Machines alternantes
- définition
- automates alternants
- classes de complexité
- fonctions récursives
- définition
- équivalence avec les machines de Turing
Cours n° 12 (jeudi 11 janvier) : théories des jeux
- théorème de Martin sur les jeux boréliens
- jeux à parités
- définition
- jeux d'accessibilité
- jeux de Büchi
- preuve de la déterminisation
- applications aux automates de mots infinis
- définitions
- complémentation par les automates à parité faible