909 -- Langages rationnels. Exemples et applications. : Différence entre versions
De AgregmathKL
| Ligne 1 : | Ligne 1 : | ||
| − | = Plans | + | = 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 68 : | Ligne 64 : | ||
#* Application à la compilation | #* 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]] | # [[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. | #* Le caractère PSPACE est admis pour des raisons de temps. | ||
| Ligne 81 : | Ligne 84 : | ||
#* 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) | + | * 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: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)
