Soutenance mémoire
Notations et préliminaires
Mots et langages et automates
Un alphabet A est un ensemble fini d’éléments appelés lettres. Un mot sur l’alphabet A est un élément du monoïde libre A∗ , c’est-à-dire une suite finie de lettres de A ou l’identité 1A∗ , appelée mot vide de A∗ . La longueur d’un mot u sur un alphabet A, notée |u|, est le nombre de lettres qui composent u. Si a est une lettre de A, alors nous notons |u|a le nombre d’occurrences de a dans u. Par exemple |abaa| = 4, |abaa|a = 3 et |abaa|b = 1. Un langage de mots sur l’alphabet A est un sous ensemble, fini ou infini, de A∗ . Dans ce mémoire, plusieurs sortes d’automates sont définis : les automates sur un alphabet, les automates dont les sorties peuvent être étiquetées par un mot, les K-automates ainsi que les transducteurs. Nous donnons ici la définition des automates booléens les plus simples.
Définition 1. Un automate fini A sur un alphabet A est un quintuplet hQ, A, E, I, Ti où :
(i) Q est un ensemble fini dont les éléments sont appelés états;
(ii) E est un ensemble d’arcs entre des éléments de Q étiquetés par A, ce sont les transitions de A ;
(iii) I est un sous-ensemble de Q, l’ensemble des états initiaux ;
(iv) T est un sous-ensemble de Q, l’ensemble des états finaux.
Les langages rationnels sur A∗ sont exactement les langages dénotés par une expression rationnelle sur A∗ . Il peut y avoir plusieurs expressions rationnelles qui dénotent le même langage rationnel. Deux expressions rationnelles sont dites équivalentes si elles dénotent le même langage. Afin de simplifier les manipulations sur les expressions rationnelles, nous définissons des identités triviales, que nous notons (T), et pour lesquelles les expressions rationnelles sont équivalentes de manière évidente et tous les calculs réalisés par la suite seront réalisés modulo (T) :
E + 0 ≡ 0 + E ≡ E , E · 0 ≡ 0 · E ≡ 0 , E · 1 ≡ 1 · E ≡ E , 0∗ ≡ 1 . (T)
Une expression est dite réduite par ces identités triviales si elle ne contient aucune sous-expression de la forme d’un membre gauche d’une de ces identités. En particulier, ces expressions permettent d’assurer qu’une expression différente de 0 n’a pas pour sous-expression 0, ce qui va nous permettre de traiter ce cas différemment lors de nos preuves par induction sur la profondeur des expressions. Il apparaît que toute expression rationnelle E peut être réécrite dans une expression réduite équivalente E′ et que cette expression réduite est unique indépendamment de l’ordre dans lequel sont appliquées les différentes identités. Finalement, il est possible de définir inductivement un booléen, appelé le terme constant d’une expression rationnelle E, noté c(E), par :
c(0) = 0 , c(1) = 1 , ∀a ∈ A c(a) = 0 ,
c(F + G) = c(F) ∨ c(G) , c(F · G) = c(F) ∧ c(G) , c(F∗) = 1 .
Proposition 2. Le terme constant d’une expression E est égal à 1 si, et seulement si, le mot vide 1A∗ est dans le langage |E|.
Nous avons pris soin de donner des définitions sur les expressions rationnelles de manière inductive car nous allons pouvoir ainsi utiliser les objets définis dans des preuves par induction. Ces définitions inductives permettent également de faire les calculs sur l’arbre syntaxique de bas en haut, ce qui sera utilisé lorsque nous donnerons une méthode pour calculer l’automate des termes dérivés. Finalement nous rappelons le théorème de Kleene qui est le théorème fondamental à la base de la théorie des automates :
Théorème 3 (Kleene). Pour tout alphabet fini, l’ensemble des langages rationnels est égal à l’ensemble des langages reconnaissables.
Il est donc possible de représenter un même langage rationnel par un automate fini qui le reconnaît ou par une expression rationnelle qui le dénote. C’est ce théorème qui nous amène à envisager la possibilité de construire des automates à partir d’expressions rationnelles, ou de construire des expressions rationnelles à partir d’automates en gardant le langage représenté.
Automate des positions
Dans cette section nous allons donner l’exemple le plus classique d’automate construit à partir d’une expression rationnelle. Cet automate, que nous appellerons l’automate des positions d’une expressions rationnelle, a été défini simultanément et indépendamment par Glushkov [26] – il est, pour cette raison, souvent appelé automate de Glushkov de l’expression – et MacNaughton et Yamada [34]. Cet automate est intrinsèquement très lié à l’expression rationnelle et en particulier il existe plusieurs algorithmes très différents pour le construire à partir de l’expression. Nous décrirons ici la méthode originale pour le construire. L’automate des positions est standard, c’est-à-dire qu’il a un unique état initial i et qu’aucune transition ne pointe vers i. Dans [43], l’automate des positions est également appelé automate standard de l’expression et, il est possible de le calculer par une méthode inductive à l’aide de constructions de bases sur les automates standard pour les opérations rationnelles. Pour construire l’automate, nous devons tout d’abord définir les positions d’une expression rationnelle. Une expression rationnelle E peut être linéarisée – c’est-à-dire que chaque lettre n’apparaît qu’au plus une fois dans E – sur un alphabet plus grand (de la taille de l’expression) en une expression rationnelle E en indiçant les occurrences de chaque lettre. Le nouvel alphabet ainsi créé est appelé l’ensemble des positions de l’expression E. Une autre manière de voir ces positions est sur l’arbre syntaxique : les positions sont les feuilles qui sont étiquetées par une lettre de l’alphabet. L’ensemble des positions est noté fp(E) et appelé l’ensemble des feuilles propres de E.
Définition 4. Soit E une expression rationnelle. L’ensemble First(E) des premières positions de E, l’ensemble Last(E) des dernières positions de E et l’ensemble Follow(l, E) des positions qui suivent l dans E, où l est une position, sont définis inductivement par :
First(0) = First(1) = ∅ ,
First(a) = {a}, a ∈ fp(E) ,
First(F + G) = First(F) ∪ First(G) ,
First(F · G) = First(F) ∪ c(F)First(G) ,
First(F∗) = First(F) ,
Last(0) = Last(1) = ∅ ,
Last(a) = {a}, a ∈ fp(E) ,
Last(F + G) = Last(F) ∪ Last(G) ,
Last(F · G) = Last(G) ∪ c(G)Last(F) ,
Last(F∗) = Last(F) ,
C’est-à-dire que First(E) est l’ensemble des positions qui sont les premières positions d’un mot dans le langage dénoté par l’expression linéarisée E. L’ensemble Last(E) est l’ensemble des positions qui sont les dernières positions d’un mot dans |E|. Si l est une position alors Follow(l, E) est l’ensemble des positions telles qu’il existe un mot dans |E| pour lequel elles suivent la position l. Pour la suite, et lorsqu’il n’y aura pas de confusion possible, nous nous autoriserons à parler de positions dans les mots du langage |E| pour parler des positions correspondantes dans les mots de |E|.
Exemple 3 (Ex. 1 cont.). Considérons l’expression rationnelle ((a+b)∗ · b)· (a + b)∗ . Afin de différencier les feuilles qui représentent une même lettre, nous donnons un indice à chaque occurrence de lettres dans cette expression rationnelle – linéarisation – : E1 = ((a1 + b1)∗ · b2) · (a2 + b3)∗ . Nous avons alors :
First(E1) = {a1, b1, b2} ,
Last(E1) = {b2, a2, b3} ,
Follow(a1, E1) = Follow(b1, E1) = {a1, b1, b2} ,
Follow(a2, E1) = Follow(b2, E1) = Follow(b3, E1) = {a2, b3} .
Il est alors possible de définir l’automate des positions :
Définition 5. L’automate des positions d’une expression rationnelle E est l’automate tel que :
(i) les états sont les positions de E et l’unique état initial i ;
(ii) les états finaux sont les positions dans Last(E);
(iii) il y a une transition de i aux positions l étiquetée par a, la lettre associée à l, si l ∈ First(E).
(iv) il y a une transition entre une position l et une position l′ étiquetée par a, la lettre associée à l′ , si l′ ∈ Follow(l, E).
Exemple 4 (Ex. 1 cont.). L’automate des positions de l’expression ((a +b) ∗· b) · (a + b)∗ est montré sur la Figure 1.2. On remarque en particulier grâce à cet exemple que les transitions entrantes dans un état sont toujours étiquetées par la lettre de la position représentée par l’état.
Proposition 4. L’automate des positions d’une expression rationnelle E est un automate standard à ℓ(E) + 1 états qui reconnaît |E|.
|
Table des matières
INTRODUCTION
I Les termes dérivés cassés d’une expression rationnelle
1 Notations et préliminaires
1.1 Mots et langages et automates
1.2 Expressions rationnelles
1.3 Automate des positions
1.4 Forme normale
1.5 Multiplicités
1.5.1 Séries formelles
1.5.2 K-automates et K-représentations
2 Termes dérivés
2.1 Dérivation des expressions
2.1.1 Expression dérivée d’une expression
2.1.2 Nombre d’expressions dérivées
2.1.3 Automates des expressions dérivées
2.2 Termes dérivés d’une expression
2.2.1 Définition et propriétés
2.2.2 Automate des termes dérivés
2.3 Dérivation et associativité du produit
2.3.1 Termes dérivés
2.3.2 Expressions dérivées
3 Termes dérivés cassés
3.1 Définitions et propriétés
3.1.1 Cassage d’une expression
3.1.2 Termes dérivés cassés
3.1.3 Automate des termes dérivés cassés
3.1.4 Associativité du produit
3.2 Taille de l’automate des termes dérivés cassés
3.2.1 Dans le cas général
3.2.2 Pour les expressions en forme normale
3.2.3 Comparaison avec les termes dérivés
4 Construction des automates des termes dérivés et termes dérivés cassés
4.1 Concaténation à droite de sous-expressions
4.1.1 Sous-expressions sur l’arbre syntaxique
4.1.2 Représentation canonique
4.2 Calcul de D(E) et Db(E)
4.2.1 Calculs sur l’arbre syntaxique décoré
4.2.2 Construction de l’automate des termes dérivés
4.2.3 Termes dérivés cassés
5 Multiplicités
5.1 K-expressions rationnelles
5.1.1 Définitions et notations
5.1.2 Représentation canonique
5.2 Termes dérivés
5.2.1 Définition
5.2.2 Calcul de l’automate
5.3 Termes dérivés cassés
5.3.1 Définition
5.3.2 Calcul de l’automate
II Enumération dans les langages rationnels
6 Systèmes de numération abstraits et fonctions rationnelles
6.1 Systèmes de numération abstraits
6.1.1 Définition
6.1.2 Enumération
6.2 Relations rationnelles
6.2.1 Relations et fonctions rationnelles
6.2.2 Transducteurs finis
6.2.3 Fonction successeur
7 Fonctions séquentielles par morceaux
7.1 Fonctions séquentielles
7.1.1 Séquentialité
7.1.2 Caractérisation
7.1.3 Décidabilité
7.2 Fonctions séquentielles par morceaux
7.2.1 Définition
7.2.2 Cascades de transducteurs séquentiels
7.2.3 coSeqpm et Seqpm
7.2.4 Décidabilité
8 Fonction successeur de langages rationnels
8.1 Produit synchronisé d’automates monocyles
8.1.1 Définitions
8.1.2 Séquentialité du produit de deux automates monocycles
8.1.3 Les langages avec un mot par longueur au plus
8.2 Concaténation de transducteurs co-séquentiels
8.3 La fonction successeur uniforme
9 Séries énumératrices des langages rationnels
9.1 Rationalité
9.1.1 Représentation de la série énumératrice
9.1.2 Calcul de la valeur d’un mot
9.1.3 Sous-ensembles reconnaissables d’entiers
9.2 Décidabilité
CONCLUSION
Télécharger le rapport complet
