908 -- Automates Finis, exemples et applications

De AgregmathKL
Aller à : navigation, rechercher

Plan d'Emmanuel et Ivan (2012)

Le Plan

On se place sur un alphabet fini \Sigma .

I - Automates finis et langages reconnaissables

I.1 - Définitions et Propriétés

  1. Définitions : Automates finis, calcul/chemin, mots acceptés, langages reconnu par un AF, Rec(\Sigma ^{*}), AF complet, émondé, à epsilon transitions, déterministe.
  2. Thm : tout AF peut etre émondé, complété, déterminisé, desespsilonisé.
    • Exemples de chaque type et leurs images par le théorème.
    • Remarque : tout déterminisé d'un AF a au plus 2^{n} états.
  3. Prop : Problème du vide et problème du mot sont décidables
    • Complexité en Nlogspace.

I.2 - Propriétés de clôtures et lemme d'itération

  1. Lemme de l'étoile
  2. Propriétés de clôture de Rec(\Sigma ^{*})

II - Langages Rationnels

  1. Déf : Rat(\Sigma ^{*})
  2. Thm de Kleen
  3. exemples : \{a^{n}b^{n},n\geq 0\}


III - Automate minimal

But : {\mathcal  {A}} AF, trouver {\mathcal  {A}}' AFDC de même langage et minimal pour le nombre d'état

  1. Déf et prop sur les quotients à gauches
    • Déf, prop classiques
    • Thm : l'automate minimal est l'automate des quotients
    • Prop : caract des langages rationnels par la finitude de l'ensemble des quotients à gauche
  2. Congruence de Nérode
    • Déf congruence
    • Déf congruence de Nérode
    • Prop : l'algo de Moore calcule la congruence de Nérode en {\mathcal  {O}}(|\Sigma ||Q|^{2}).

IV - Applications ...

IV.1 - ... à la logique

  1. Thm de Presburger [Dev 1]

IV.2 - ... à l'analyse lexicale

  1. Définir les notions et insister sur la place de l'analyse lexicale dans la chaîne de compilation
  2. Exemple si la place

IV.3 - à l'algorithmique du texte

  1. Algo naïf de recherche d'un mot dans un texte + complexité
  2. Algo par automate + complexité
  3. Algo Morris et Pratt + complexité
  4. Conclure sur le fait que les automates sont pas trop mal pour ce type de problème.

IV.4 - ... à la classification

  1. Déf de la séparation de deux langages par un automate (PSA)
  2. PSA est NP-Complet [Dev 2]

Développements possibles

  • Thm de Presburger [Carton] - se place dans les leçons [908], [909] (moins), [914], [924]
  • PSA est NP-Complet [Sakarovitch] - se place dans les leçons [908], [915]
  • Thm de Kleen - se place dans les leçons [908], [909], autre ? - développement très peu innovant, les jury ne l'aiment pas.
  • Congruence de Nérode
  • Knuth-Morris-Pratt - je ne garanti pas qu'il soit faisable en développement mais si oui il se recase en algo du texte, et complexité.

Références

  • Luc Albert - pour la quasi totalité du plan
  • Carton - pour Presburger et compléments du plan
  • Sakarovitch - Pour PSA est NP-complet - pas très lisible pour faire un plan
  • David, Nour, Raffalli - Introduction à la logique - Pour les bases de la logique pour Presburger (pour les questions qui viendrons après)