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. Dans ce mémoire, nous ne traitons pas le cas des automates infinis et nous appellons automates les automates finis. La Figure 1.1 montre comment nous représentons les automates. Les états initiaux sont repérés par des flèches entrantes, les états finaux par des flèches sortantes. 17 Notations et préliminaires b a a b b Figure 1.1 – Un automate, B1 sur l’alphabet {a, b} Un état p d’un automate A est dit acccessible s’il existe un chemin dans l’automate d’un état initial de I à p. Il est co-accessible s’il existe un chemin de p à un élément de T. Un automate A est accessible si tous ses états le sont, co-accessible si tous ses états le sont et émondé si il est à la fois accessible et co-accessible. Un calcul réussi de A est un chemin qui commence dans un état initial et qui se termine dans un état final. Le langage reconnu par A, noté |A| est le sous-ensemble de A∗ des étiquettes des calculs réussis : |A| = n u ∈ A ∗ | i u→ t, i ∈ I, t ∈ T o . Par exemple le langage reconnu par l’automate B1 de la Figure 1.1 est |B1| = A∗{b}A∗ , c’est-à-dire le langage des mots sur A qui contiennent au moins un b. Un langage de A∗ est dit reconnaissable s’il existe un automate fini qui le reconnaît. Un automate est dit déterministe s’il a un unique état initial i et si, pour tout état p, il existe, au plus, une unique transition sortante étiquetée par chaque lettre de A. Un automate est dit ambigu si il existe un état q et un mot u tel qu’il y ait plus d’un chemin d’un état initial à q étiqueté u. Un automate déterministe est non-ambigu. Proposition 1. Il est possible de transformer tout automate fini A en un automate fini déterministe B qui reconnaît le même langage. Si l’automate A a n états, il est possible de construire B avec au plus 2 n états. Les langages reconnaissables sont donc les langages reconnus par les automates finis déterministes. Il peut y avoir plusieurs automates déterministes qui reconnaissent le même langage.

Expressions rationnelles

Afin de définir les expressions rationnelles et les langages rationnels sur un alphabet, nous définissons tout d’abord les opérations rationnelles sur les sous-ensembles d’un monoïde : 18 Définition 2. Les opérations rationnelles sur les sous-ensembles d’un monoïde M sont l’union, le produit d’ensembles et l’étoile définie par : X ∗ = {1M } ∪ [ n>0 X n . La famille des sous-ensembles rationnels de M, notée Rat M, est la fermeture des ensembles finis par ces opérations. En particulier, nous appelons langages rationnels sur A∗ les sousensembles rationnels de A∗ . Les expressions rationnelles sont un moyen de décrire ces langages en notant les opérations rationnelles successives pour obtenir le sous-ensemble rationnel. Plus précisément : Définition 3. Une expression rationnelle E sur A est une formule bien parenthésée obtenue inductivement par la grammaire suivante dans lesquelles les atomes sont les lettres de A et les expressions prédéfinies 0 et 1 : E → {a | a ∈ A} | 0 | 1 | (E + E) | (E · E) | (E ∗ ) . L’ensemble des expression rationnelles sur un alphabet A est noté RatE(A). Comme toute expression bien parenthésée, une expression rationnelle E peut être représentée par un arbre syntaxique, que nous notons TE. La profondeur d’une expression E, notée d(E), est la profondeur de l’arbre syntaxique, plus précisément : d(0) = 0 , d(1) = 1 , d(a) = 1 , d(E + F) = max(d(E), d(F)) + 1 , d(E · F) = max(d(E), d(F)) + 1 , d(E ∗ ) = d(E) + 1 . Exemple 1. La formule ((a+ b) ∗ · b)·(a+ b) ∗ est une expression rationnelle de profondeur 5. Par défaut, lorsque les parenthèses seront absentes, c’est le parenthésage à gauche qui sera utilisé : E · F · G = ((E · F) · G). Le justification de ce choix sera donnée par l’analyse de l’influence du parenthésage des produits sur les termes dérivés (et les termes dérivés cassés). La longueur littérale de l’expression E, notée ℓ(E), est le nombre d’occurrences de lettres de l’alphabet A 19 dans celle-ci. Le langage dénoté par une expression rationnelle E, noté |E|, est défini inductivement par : |0| = ∅ , |1| = {1A∗ } , |a| = {a} , |(E + F)| = |E| ∪ |F| , |(E · F)| = |E||F| , |(E ∗ )| = |E| ∗ . Exemple 2 (Ex. 1 cont.). Le langage dénoté par l’expression rationnelle ((a + b) ∗ · b)·(a + b) ∗ est le langage A∗ bA∗ des mots contenant au moins une occurrence de b. 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|. 20 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 21 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.