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

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."