909 -- Langages rationnels. Exemples et applications.

Plan de Kévin et Basile (2012)

Le Plan

I) Expressions Rationnelles

1. Définitions
   • Par induction
   • Par récurrence et hauteur
2. Sémantique
   • Interprétation
   • Exemples
   • Hauteur d'étoile \[ généralisé \]
   • Langage de hauteur d'étoile $n$
3. Équations
   • Lemme d'ARDEN
   • Pivot de GAUSS
4. Réduction des expressions rationnelles
   • Décidabilité de l'équivalence
   • Exemple
   • Règle de Saloma. <ref> Sylvain Schmidt </ref>

II) Caractérisations

1. Théorème de Kleene
2. (Lemmes de l'étoile)
   • 3 versions.
   • Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire.
3. Grammaire
   • Caractérisation par les langages de grammaires linéaires gauches.
4. Automate à Pile
   • Le langage de Pile d'un automate à pile est reconnaissable

III) Cas d'un monoïde quelconque

<ref> O. Carton </ref>

1. Définitions.
2. Version faible du théorème de Kleene.
   • Exemples

IV) Applications

1. Arithmétique de Presburger.
2. Analyse Lexicale.
   • Expressions régulières
   • Exemples de commandes...
3. Séparation par automate.

Développements possibles

1. Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde)
2. Presburger
3. Langage de Pile d'un Automate à Pile
4. Théorème de Higman et corollaires :
   • Il n'existe pas d'antichaïne infinie pour l'ordre lexicographique sur le monoïde libre d'un alphabet fini.
   • Les surmots et sousmots pour l'ordre lexicographique d'un langage quelconque sont rationnels.
6. Séparation par automate
   • Montré indécidable par réduction à 3-SAT ou par réduction à SAT tout court on montre que c'est NPcomplet, cf Leçon 909 (non?)

Références

Carton... "C'est mal de ne pas mettre quelque chose qui est dans le Carton, c'est mal de mettre quelque chose qui n'est pas dans le Carton."