909 -- Langages rationnels. Exemples et applications. : Différence entre versions
De AgregmathKL
m (→Développements possibles) |
(→IV) Applications) |
||
Ligne 34 : | Ligne 34 : | ||
#* Exemples | #* Exemples | ||
=== IV) Applications === | === IV) Applications === | ||
− | # Arithmétique de | + | # Arithmétique de Presburger. |
# Analyse Lexicale. | # Analyse Lexicale. | ||
#* Expressions régulières | #* Expressions régulières |
Version du 23 octobre 2011 à 19:52
Sommaire
Plan de Kévin et Basile (2012)
Le Plan
I) Expressions Rationnelles
- Définitions
- Par induction
- Par récurrence et hauteur
- Sémantique
- Interprétation
- Exemples
- Hauteur d'étoile \[ généralisé \]
- Langage de hauteur d'étoile
- Équations
- Lemme d'ARDEN
- Pivot de GAUSS
- Réduction des expressions rationnelles
- Décidabilité de l'équivalence
- Exemple
- Règle de Saloma. <ref> Sylvain Schmidt </ref>
II) Caractérisations
- Théorème de Kleene
- (Lemmes de l'étoile)
- 3 versions.
- Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire.
- Grammaire
- Caractérisation par les langages de grammaires linéaires gauches.
- Automate à Pile
- Le langage de Pile d'un automate à pile est reconnaissable
III) Cas d'un monoïde quelconque
<ref> O. Carton </ref>
- Définitions.
- Version faible du théorème de Kleene.
- Exemples
IV) Applications
- Arithmétique de Presburger.
- Analyse Lexicale.
- Expressions régulières
- Exemples de commandes...
- Séparation par automate.
Développements possibles
- Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde)
- Prestburger
- Langage de Pile d'un Automate à Pile
- 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.
- 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."