909 -- Langages rationnels. Exemples et applications. : Différence entre versions
De AgregmathKL
(→Développements possibles) |
|||
(16 révisions intermédiaires par 6 utilisateurs non affichées) | |||
Ligne 1 : | Ligne 1 : | ||
− | = | + | = Plans = |
− | == | + | [[Fichier:Pdf.png|alt=Pdf|link=Média:909_2012-2013.pdf|24px]] [[Média:909_2012-2013.pdf|Plan scanné de l'année 2012-2013]] |
+ | |||
+ | [[Fichier:Pdf.png|alt=Pdf|link=Média:909_2013-2014.pdf|24px]] [[Média:909_2013-2014.pdf|Plan scanné de l'année 2013-2014]] et [[Fichier:Pdf.png|alt=Pdf|link=Média:909_2013-2014_bis.pdf|24px]] [[Média:909_2013-2014_bis.pdf|Plan bis de l'année 2013-2014]] | ||
+ | |||
+ | [[Fichier:Pdf.png|alt=Pdf|link=Média:909_2014-2015.pdf|24px]] [[Média:909_2014-2015.pdf|Plan scanné de l'année 2014-2015]] | ||
+ | |||
+ | [[Fichier:Pdf.png|alt=Pdf|link=Média:909_2015-2016.pdf|24px]] [[Média:909_2015-2016.pdf|Plan scanné de l'année 2015-2016]] | ||
+ | |||
+ | [[Fichier:Pdf.png|alt=Pdf|link=Média:909_2018-2019.pdf|24px]] [[Média:909_2018-2019.pdf|Plan scanné de l'année 2018-2019]] | ||
+ | |||
+ | |||
+ | == Autre plan : Kévin et Basile (2012) == | ||
=== I) Expressions Rationnelles === | === I) Expressions Rationnelles === | ||
Ligne 10 : | Ligne 21 : | ||
#* Interprétation | #* Interprétation | ||
#* Exemples | #* Exemples | ||
− | #* Hauteur d'étoile | + | #* Hauteur d'étoile (généralisé ... bof) |
− | #* Langage de hauteur d'étoile <math>n</math> | + | #* Langage de hauteur d'étoile <math>n</math> |
# Équations | # Équations | ||
#* Lemme d'ARDEN | #* Lemme d'ARDEN | ||
Ligne 18 : | Ligne 29 : | ||
#* Décidabilité de l'équivalence | #* Décidabilité de l'équivalence | ||
#* Exemple | #* Exemple | ||
− | #* | + | #* Le problème d'universalité est PSPACE-Complet (DEV) |
+ | # Ordre sous-mot | ||
+ | #* Définition, de l'ordre, des antichaînes (ensemble d'éléments incomparables deux à deux ) | ||
+ | #* Théorème de Higman et ses corollaires ( les sous-mots et les sur-mots d'un langage sont rationnels ) | ||
+ | |||
=== II) Caractérisations === | === II) Caractérisations === | ||
# Théorème de Kleene | # Théorème de Kleene | ||
− | # | + | #* Dérivées d'Antimirov et résolutions d'équations par le lemme d'Arden |
− | #* | + | # Lemme de l'étoile [Carton p. 54] |
− | #* Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire. | + | #* version par bloc |
− | # Grammaire | + | #* Théorème (EPR) : Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire. |
+ | # Grammaire régulières | ||
#* Caractérisation par les langages de grammaires linéaires gauches. | #* Caractérisation par les langages de grammaires linéaires gauches. | ||
# Automate à Pile | # Automate à Pile | ||
− | #* Le langage de Pile d'un automate à pile est reconnaissable | + | #* Définition langage de Dyck et langage de Pile |
− | + | #* Le langage de Pile d'un automate à pile est reconnaissable (DEV) | |
− | + | # Reconnaissance par monoïde | |
− | # | + | #* Définition |
− | # | + | #* Théorème de caractérisation : reconnaissance par monoïde fini. |
+ | #* Exemple | ||
+ | #* Propriétés de stabilité par morphismes | ||
+ | # Théorème de Myhill-Nérode [Carton p. 45] | ||
+ | #* Définition résiduels | ||
#* Exemples | #* Exemples | ||
+ | #* Caractérisation par finitude du nombre de résiduels | ||
+ | === III) Cas d'un monoïde quelconque [Carton p. 72] === | ||
+ | # Définitions : Reconnaissance par monoïde fini, Rationalité... | ||
+ | # Version faible du théorème de Kleene. | ||
+ | #* Exemples et contre-exemples | ||
=== IV) Applications === | === IV) Applications === | ||
− | |||
# Analyse Lexicale. | # Analyse Lexicale. | ||
#* Expressions régulières | #* Expressions régulières | ||
#* Exemples de commandes... | #* Exemples de commandes... | ||
− | # | + | #* Application à la compilation |
+ | |||
+ | |||
+ | |||
+ | = Développements = | ||
+ | <DynamicPageList> | ||
+ | category = Développement de la leçon 909 | ||
+ | </DynamicPageList> | ||
+ | |||
+ | = Autres développements = | ||
+ | # [[Universalité d'un langage rationnel | Le problème d'universalité d'un langage rationnel est PSPACE-dur]] | ||
+ | #* Le caractère PSPACE est admis pour des raisons de temps. | ||
+ | # Langage de Pile d'un Automate à Pile ([[Média:Dvt_langage_de_pile.tex | Source .tex]] ; [[Média:Dvt_langage_de_pile.pdf | .pdf]]) | ||
− | |||
# Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde) | # Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde) | ||
− | # | + | # [[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. | |
− | + | ||
− | #* Il n'existe pas d' | + | |
#* Les surmots et sousmots pour l'ordre lexicographique d'un langage quelconque sont rationnels. | #* Les surmots et sousmots pour l'ordre lexicographique d'un langage quelconque sont rationnels. | ||
− | # | + | # (Presburger) |
− | # Séparation par automate | + | # (Séparation par automate) |
− | #* Montré indécidable par réduction à 3-SAT | + | #* 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." (D. Cachera) | ||
+ | |||
− | + | [[Category:Leçon d'informatique]] | |
− | + | [[Category:Anciennes leçons]] |
Version actuelle en date du 22 avril 2022 à 10:43
Sommaire
Plans
Plan scanné de l'année 2012-2013
Plan scanné de l'année 2013-2014 et Plan bis de l'année 2013-2014
Plan scanné de l'année 2014-2015
Plan scanné de l'année 2015-2016
Plan scanné de l'année 2018-2019
Autre plan : Kévin et Basile (2012)
I) Expressions Rationnelles
- Définitions
- Par induction
- Par récurrence et hauteur
- Sémantique
- Interprétation
- Exemples
- Hauteur d'étoile (généralisé ... bof)
- Langage de hauteur d'étoile
- Équations
- Lemme d'ARDEN
- Pivot de GAUSS
- Réduction des expressions rationnelles
- Décidabilité de l'équivalence
- Exemple
- Le problème d'universalité est PSPACE-Complet (DEV)
- Ordre sous-mot
- Définition, de l'ordre, des antichaînes (ensemble d'éléments incomparables deux à deux )
- Théorème de Higman et ses corollaires ( les sous-mots et les sur-mots d'un langage sont rationnels )
II) Caractérisations
- Théorème de Kleene
- Dérivées d'Antimirov et résolutions d'équations par le lemme d'Arden
- Lemme de l'étoile [Carton p. 54]
- version par bloc
- Théorème (EPR) : Caractérisation par le lemme de l'étoile par blocs appliqué au langage et à son complémentaire.
- Grammaire régulières
- Caractérisation par les langages de grammaires linéaires gauches.
- Automate à Pile
- Définition langage de Dyck et langage de Pile
- Le langage de Pile d'un automate à pile est reconnaissable (DEV)
- Reconnaissance par monoïde
- Définition
- Théorème de caractérisation : reconnaissance par monoïde fini.
- Exemple
- Propriétés de stabilité par morphismes
- Théorème de Myhill-Nérode [Carton p. 45]
- Définition résiduels
- Exemples
- Caractérisation par finitude du nombre de résiduels
III) Cas d'un monoïde quelconque [Carton p. 72]
- Définitions : Reconnaissance par monoïde fini, Rationalité...
- Version faible du théorème de Kleene.
- Exemples et contre-exemples
IV) Applications
- Analyse Lexicale.
- Expressions régulières
- Exemples de commandes...
- Application à la compilation
Développements
- Algorithme de Hopcroft
- Arithmétique de Presburger
- Théorème de Higman
- Universalité d'un langage rationnel
- Problème de séparation par automate
Autres développements
- Le problème d'universalité d'un langage rationnel est PSPACE-dur
- Le caractère PSPACE est admis pour des raisons de temps.
- Langage de Pile d'un Automate à Pile ( Source .tex ; .pdf)
- Caractérisation de la rationalité par le lemme de l'étoile par blocs (immonde)
- 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.
- (Presburger)
- (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." (D. Cachera)