Concept et modèles d’automate déterministe

Télécharger le fichier original (Mémoire de fin d’études)

Généricité en C++

Patrons (templates) de classe et de fonction

Les patrons [68] de classe sont des métatypes paramétrés par un ou plusieurs types. L’uti-lisateur de ces métaclasses, en fournissant explicitement ces types au moment de l’utilisation, instancie le patron et en fait un type concret utilisable. Ce mécanisme permet d’écrire des containers indépendamment du type des objets stockés et de ne prendre une décision concer-nant le rˆole de l’objet qu’au dernier moment. Dans l’exemple suivant, deux patrons standards list sont instanciés, le premier objet est configuré pour contenir des entiers, le deuxième pour contenir des listes de flottants :
list<int> a;
list<list<float> > b;
Les patrons de fonctions acceptent n’importe quel type d’argument pourvu qu’il implémente les opérations nécessaires a` l’exécution de la fonction. L’instanciation d’un patron de fonction se fait implicitement, l’utilisateur n’est pas obligé de préciser les types voulus, le compila-teur les déduit automatiquement des arguments d’appel. Ces fonctions permettent d’écrire des algorithmes indépendants des types auxquels ils s’appliquent. Par exemple, le patron de fonction min suivant renvoie la valeur du plus petit des deux arguments d’appel. Il impose au type T, détermin´ a` l’utilisation, de définir une relation d’ordre matérialisée par l’opérateur < :
template <class T>
T min(const T &x, const T &y) {
return x < y ? x : y;
}

Les itérateurs

Itérateur est le nom oﬃciel de l’accesseur en C++. Tous les containers fournissent un type d’itérateur permettant le parcours des données contenues. Ils permettent d’écrire des algorithmes indépendamment des types des containers et des objets stockés. L’algorithme copy copie une séquence source définie par une paire d’itérateurs [first, last) appelée intervalle vers une séquence cible accessible a` travers l’itérateur out :
template <class InputIterator, class OutputIterator>
void copy(InputIterator first, InputIterator last, OutputIterator out)
{
for(; first != last; ++first)
*out++ = *first;
1.2. MISE EN ŒUVRE 17
}
La notation [first, last) désigne l’ensemble des positions partant de first mais n’incluant pas last qui ne sert que de marqueur de fin de séquence5.
L’algorithme ne fait aucune supposition sur le type des eléments de la séquence ni sur la structure de données. Les seules conditions requises portent sur le type InputIterator qui doit implémenter trois opérateurs ++, *, != et sur le type des objets copiés qui doit ˆetre assignable (opérateur d’aﬀectation =).

Expansion en ligne (inlining)

La programmation générique en C++ est viable car la compilation du code génère des exécutables eﬃcaces et ce grˆace, notamment, a` l’expansion ou insertion en ligne (inlining) qui consiste a` remplacer dans le fichier binaire les appels a` certaines fonctions par le corps de ces fonctions. Le résultat est similaire a` celui obtenu en utilisant des macros en C mais sans en subir les inconvénients puisque ces pseudo-macros sont de vraies fonctions et qu’elles bénéficient donc de tous les garde-fou habituels de la compilation, entre autres les vérifications de type.
Toutes les fonctions ou méthodes ne sont pas expansées en ligne, seules celles que le compila-teur juge suﬃsamment simples le sont ; il n’est par exemple évidemment pas possible d’insérer en ligne une fonction récursive.
Chose peu courante, cette optimisation est non seulement terriblement eﬃcace (il est cou-rant d’observer des facteurs d’accélération de 10 ou 20 entre une compilation avec inlining et sans), mais elle permet une plus grande encapsulation du code et donc une conception plus robuste : elle réduit a` néant le coˆut des appels aux méthodes aussi simples que l’accès a` l’attribut d’un objet ou la transmission d’un appel (forwarding). Il est donc possible grˆace a` cette optimisation de se passer d’accéder directement aux données contenues dans un objet ce qui est considér´ comme une discipline saine en programmation objet.

La Standard Template Library

La STL est une librairie générique de containers et d’algorithmes sur les séquences in-tégrée au langage C++. Son intérˆet repose plus sur les concepts et les spécifications qui la constituent que sur le code en lui-mˆeme. On dit d’ailleurs souvent « STL is not a set of pro-grams, it is a set of requirements » et on considère souvent comme équivalentes les notions de concept et de spécification qui n’est autre que la matérialisation d’un concept et qui constitue principalement STL. Elle définie une hiérarchie d’abstractions par raﬃnements successifs sur les propriétés que doivent vérifier les types concrets (les modèles) se conformant aux concepts.
L’espace des composants est découp´ en cinq grands concepts : les algorithmes, les itéra-teurs, les containers, les allocateurs [32] et les adaptateurs qui projettent un concept vers un autre. Ces familles de types abstraits sont constituées de sous-ensembles regroupant les types partageant des caractéristiques précises. Par exemple, le concept assignable désigne tous les types concrets dont on peut assigner la valeur a` un objet du mˆeme type (il définit un opérateur =). Ces ensembles incluent également des sous-ensembles obtenus par raﬃnement du concept. La figure 1.4 montre un extrait de la hiérarchie STL du concept de container séquentiel. Un container est un objet capable de stocker d’autres objets et fournit des méthodes d’accès auxdits objets ainsi qu’un type d’itérateur. Un forward container est un container dont les eléments sont rangés dans un ordre défini ne changeant pas spontanément d’un parcours a` l’autre. Il ne permet l’énumération de ses objets que dans un sens alors que le reversible container autorise l’itération dans les deux sens. Une sequence est un container supportant l’insertion et la suppression d’élément. Enfin, une front insertion sequence autorise l’insertion d’éléments en tˆete et en temps constant alors qu’une back insertion sequence ne le permet qu’en queue. En bas de la hiérarchie, le type concret list modélise tous ces concepts, c’est-a`-dire qu’il vérifie les propriétés de tous les concepts dont il dérive. Il est possible de traverser la liste dans les deux sens car il s’agit d’une liste doublement chaˆınée et il est possible d’y insérer des eléments partout en temps constant.
STL définit de telles hiérarchies sur les itérateurs, les containers séquentiels et associatifs (arbres, tables de hachage, etc.) et les adaptateurs. Les algorithmes sont codés avec des pa-trons de fonction prenant en argument des intervalles, c’est-a`-dire des paires d’itérateurs marquant le début et la fin de la séquence sur laquelle s’applique le traitement. Ce découpage orthogonal des composants est con¸cu pour ne pas ˆetre figé et se destine a` ˆetre étendu a` tous les domaines de programmation, ce que nous nous proposons de faire pour les automates.

Automates génériques

Les motivations a` développer une librairie générique d’automates reposent sur les consta-tations suivantes :
– L’automate est un modèle mathématique et informatique « versatile » (au sens anglo-saxon du terme), il trouve son utilité dans un nombre impressionnant de domaines variés o`u les besoins et contraintes sont multiples, d’o`u la nécessit´ d’un code adaptatif.
– La demande pour des applications eﬃcaces reste plus que jamais d’actualité avec l’émer-geance des technologies de traitement de la langue naturelle et l’augmentation vertigi-neuse des quantités de données a` traiter. La programmation générique en C++ a l’avan-tage de fournir des implémentations dont les performances sont comparables a` celles du C ou du Fortran [77] et ceci aussi bien en vitesse qu’en mémoire.
– Il existe un lien évident entre tous les modèles mathématiques basés sur des structures de graphe. La base étant la mˆeme, il est possible de concevoir des concepts communs a` tous ces modèles ainsi que des structures de données qui leur correspondent.
– Il n’existe aucune librairie réellement générique, c’est-a`-dire combinant adaptabilité et eﬃcacit´. Les recettes qui ont contribué au succès de la programmation générique sur les séquences n’ont pas et´ appliquées rigoureusement et exhaustivement aux graphes, aux automates et aux machines en général.

Domaine

Cette section décrit exhaustivement l’ensemble des librairies oﬃciellement disponibles pour l’utilisation et le traitement des graphes et des automates. Elle expose leurs particularités et les faiblesses motivant la conception d’une nouvelle librairie réellement générique :
– La « Library of Eﬃcient Data Types and Algorithms » (LEDA, [36]) est une des plus anciennes librairies de structures de données génériques écrites en C++. Elle couvre un domaine d’application très large et notamment les graphes mais ne supporte pas de mécanisme de généricit´ assez développ´. Antérieure a` STL, sa conception et son ar-chitecture n’incorpore pas les récentes avancées de la programmation générique en C++.
– L’ex « Generic Graph Components Library » (GGCL, [58]) devenue la « Boost Graph Library » (BGL, [59]). Il s’agit probablement de la librairie la plus sophistiquée et la plus eﬃcace. Ecrite en C++, ses principes de conception comprennent notamment l’utilisa-tion du patron de conception visiteur pour les parcours [19] et la possibilité d’associer des paramètres multiples aux nœuds et aux arcs. Elle ne comprend malheureusement que deux représentations diﬀérentes de graphes (liste d’adjacence ou container d’arcs) et ne propose pas réellement de nouveaux concepts ni de méthodes neuves de program-mation. Il manque en particulier un concept unique d’itérateur généralis´ aux graphes.
– La « Graph Template Library » (GTL, [16]) est a` mi-chemin entre LEDA et BGL. Le niveau de généricit´ est plus elev´ que pour la premi`re ; il y est fait usage de concepts comme les itérateurs (sur les arcs et les nœuds) permettant une interaction directe avec les algorithmes de STL et donc un niveau de réutilisation raisonnable. Malheu-reusement la modularité nécessaire au découplage structure/algorithme est loin d’ˆetre satisfaisante car elle repose sur un modèle a` deux couches qui implique d’incorporer un certains nombres d’algorithmes au container comme par exemple la sauvegarde et le chargement, or le modèle a` deux couches montre très vite ses limites et son manque de souplesse, notamment en ce qui concerne les algorithmes de parcours génériques.
– La « Patterns Template Library » (PTL, [65]) est basée sur les structures de données dites intrusives [64]. Elle ne constitue pas vraiment une librairie complète de machine a` états mais plutˆot un exercice d’application pour un style de conception particulier cher a` son auteur. Elle est, de ce fait, extrˆemement limitée.
– « Grail+ » [51] est un environnement de calcul sur les automates sous forme de filtres UNIX accompagnés d’une collection de composants écrits en C++ mais non-génériques. Les patrons de classe ne sont paramétrés que par le type d’objet étiquetant les transi-tions, le concept d’accesseur est inexistant et les algorithmes sont incorporés aux classes.
– « Fire Lite » [78] est écrite en C++ et implémente les algorithmes décrits dans la taxono-mie des algorithmes sur les automates et les expressions rationnelles [79]. Probablement la plus complète en ce qui concerne les algorithmes de construction. La librairie est con¸cue avec soin et l’aspect performance est mis en avant mais la généricit´ est insuﬃ-sante : l’orthogonalité entre structures et algorithmes n’est pas assurée.
– « AUTOMATA » ( http://www-2.cs.cmu.edu/~sutner/automata.html) est une li-brairie écrite en Mathematica et dont les parties critiques sont codées en C++. L’ar-chitecture n’est pas générique et ne se positionne pas dans une optique de réutilisation.
– « FSA Utilities » (Finite State Automata Utilies) se présente sous forme de filtres UNIX et de librairies en Prolog permettant la manipulation d’automates, d’expressions ration-nelles et de transducteurs (http://odur.let.rug.nl/~vannoord/fsa/fsa.html).

Au-delà de la programmation générique

De nouvelles techniques de programmation apparues récemment proposent des pallia-tifs aux principales faiblesses de la programmation gén´rique et augmentent encore le degr´ d’adaptabilité des composants logiciels. La programmation générative [12, 8], grˆace a` la mé-taprogrammation [72, 35], [11] pp. 251-279, permet d’écrire des librairies actives [76] o`u un grand nombre d’opérations liées a` la conception et l’assemblage des composants est auto-matisé et relégu´ au compilateur. Ces librairies gén`rent des types extrˆemement composites construits a` partir de spécifications utilisateur haut-niveau reflétant le contexte d’utilisation. Elles intègrent en outre le paradigme de la programmation dite orientée-aspect [11] pp. 183-242, insistant sur la modularité et la maintenabilit´.
Cette expérience de programmation générique a logiquement men´ a` la conception d’une li-brairie active de machines a` états au sens large du terme capable de générer des types de containers et de curseurs optimisés couvrant la totalité des besoins du domaine.

Plan

L’idée générale de l’expos´ est de partir du modèle des automates, de voir comment on peut les implémenter de manière eﬃcace et générique en imaginant les concepts qui leur sont propres puis de généraliser a` toutes les structures de données partageant des similarités. Les diﬀérentes étapes sont :
1. Définitions mathématiques formelles, vocabulaire et propriétés des automates (chapitre 2) ;
2. Concepts liés a` l’abstraction « machine a` états », structures de données et implémen-tation des containers (chapitre 3). Premier niveau d’adaptabilité de la librairie, une batterie de containers polymorphes aux performances hétérogènes ;
3. L’abstraction accesseur d’automate, le curseur (chapitre 4) ;
4. Deuxième niveau d’adaptabilité, les adaptateurs de curseur (chapitre 5) ;
5. Généralisation de ces concepts a` toutes les structures de données basées sur des struc-tures de graphes. Palliatif aux faiblesses de la programmation générique (configuration et assemblage de composant automatiques), programmation genérative en C++ grˆace a` la métaprogrammation statique (chapitre 6).
Le modèle développ´ dans la suite de cet expos´ :
– est réellement adaptatif : les containers d’automate sont paramétrés par le type de l’al-phabet et le type de l’information associée aux états. De plus, une variét´ de containers partageant la mˆeme interface mais hétérogènes du point de vue des représentations en mémoire permet d’adapter les complexités des traitements en temps et en espace a` une multitude de situations.
– met en œuvre une architecture a` trois couches avec les curseurs comme accesseurs. Ces curseurs oﬀrent un degr´ de libert´ supplémentaire car leur comportement est modifiable a` souhait par adaptation du comportement de base. Une bonne partie des opérations pré-sentes habituellement dans les algorithmes est reléguée a` la couche curseur. Le manque de généricit´ des librairies existantes vient du fait qu’elles ne proposent pas réellement de modèle a` trois couches bien identifiées car elle n’introduisent pas de concept unique d’accesseur sur automate.
– est con¸cu pour ˆetre eﬃcace et utilisable dans un contexte « industriel » de développe-ment ; bon nombre d’optimisations ont et´ envisagées et l’implémentation repose sur des composants STL solides et eprouvés.

Les automates

Les automates et les machines a` états finies sont nés quasiment en mˆeme temps que l’in-formatique et ont et´ intensivement etudiés et utilisés durant les 50 dernières années. D’abord modèles d’étude théoriques riches et puissants, leur succès s’explique aussi par leur eﬃcacit´ pratique et le nombre impressionnant d’applications pour lesquelles ils se révèlent particulière-ment bien adaptés. Les machines a` états trouvent leur utilité dans la conception de composants électroniques, la recherche de motifs, le cryptage, la compression de donnée, la linguistique avec les analyses morphologique, syntaxique et sémantique, la correction orthographique, la reconnaissance de la parole, etc. Des graphes aux transducteurs en passant par les automates, les applications des machines a` états finies sont beaucoup trop nombreuses pour en dresser une liste exhaustive.
Ce chapitre aborde les définitions formelles des automates. Il constitue la première étape de l’expos´ qui nous mènera progressivement du modèle mathématique au modèle informatique abstrait puis a` son implémentation concrète. Il s’agit donc ici de définir le plus formellement possible les abstractions mathématiques sur lesquelles reposeront les définitions d’abstractions logicielles.

Mots et langages

Un automate sert notamment a` modéliser et a` construire une grammaire. Cette grammaire définit un langage, autrement dit un ensemble de mots autorisés que l’automate est capable de reconnaˆıtre.

Définitions

Soit Σ un ensemble appel´ alphabet dont les eléments sont appelés lettres. Un mot w sur l’alphabet Σ est une suite finie de lettres (σ1, σ2, …, σn) avec pour longueur n ≥ 0 notée |w|. On désigne la ieme` lettre du mot par wi. Si n = 0, w est appel´ mot vide et noté ǫ. L’ensemble des mots sur l’alphabet Σ est noté Σ∗ et Σ+ = Σ∗ \ {ǫ}. Le produit ou concaténation de deux mots u, v ∈ Σ∗ s’obtient en écrivant séquentiellement les lettres de u puis celles de v :
u • v = u1 u2 … un v1 v2 … vm
Par simplification et partout o`u cela ne prˆete pas a` confusion on omettra le • en écrivant uv plutˆot que u • v.
Le produit d’un mot u avec lui-mˆeme répét´ k fois s’écrit uk avec u0 = ǫ. Si w = uw′v on dit que w′ est un facteur de w, u est un préfixe de w et v est un suﬃxe de w.
Un langage sur l’alphabet Σ est un sous-ensemble de Σ∗.

Opérations sur les langages

Soient A et B deux langages. On généralise le produit de mots aux langages comme suit :
A • B = {ab | a ∈ A, b ∈ B}
On définit les opérations booléennes sur les langages par :
A ∩ B = {w | w ∈ A et w ∈ B}
A ∪ B = {w | w ∈ A ou w ∈ B}
A \ B = {w | w ∈ A et w ∈/ B}
A △ B = (A ∪ B) \ (A ∩ B) = {w | w ∈ A ∪ B et w ∈/ A ∩ B}
A = Σ∗ \ A = {w | w ∈ Σ∗ et w ∈/ A}

Automates finis

Définition

Pour accroˆıtre la généricit´ et s’adapter aux besoins algorithmiques on ajoute a` la dé-finition traditionnelle des automates la possibilité d’associer a` chaque état une information quelconque appelée « tag ». L’ensemble τ associe les états de l’automate a` leur tag de manière bijective.
Soit A(Σ, Q, I , F, Δ, T , τ ) un 7-uplet d’ensembles finis définit comme suit :
Un alphabet
Un ensemble d’états
Un ensemble d’états initiaux
Un ensemble d’états finaux ou terminaux
Un ensemble de transitions
Un ensemble de tags
Un ensemble associant les états a` leur tags respectifs
L’étiquette d’une transition (q, σ, p) est la lettre σ, q est sa source et p sa destination ou but.
Lorsque σ = ǫ (le mot vide) la transition est appelée epsilon-transition.
On appelle transitions entrantes de l’état s, l’ensemble des transitions (q, σ, p) ∈ Δ telles que p = s et inversement, on appelle transitions sortantes l’ensemble des transitions (q, σ, p) ∈ Δ telles que q = s.
On notera P (X) l’ensemble des parties d’un ensemble X et |X| son nombre d’éléments.
On définit deux fonctions de transition δ1 et δ2 fréquemment utilisées pour l’accès aux tran-sitions de l’automate :
δ1 : Q×(Σ∪{ǫ})→P(Q)
δ2 : Q → P(Σ × P(Q))
La fonction δ1 associe a` un état q et une lettre σ l’ensemble des buts des transitions etiquetées par σ sortant de q. La fonction δ2 associe a` un état q l’ensemble des couples lettre/but de ses transitions sortantes. On étend naturellement la définition de δ1 aux mots :
δ∗ : P(Q) × Σ∗ → P(Q)
(q, ǫ) q
(q, w • a) δ1(δ1∗(q, w), a)
Le contexte droit d’un état q est l’ensemble des lettres étiquetant les transitions sortant de q :
c (q) = {σ ∈ Σ | ∃p ∈ Q, (q, σ, p) ∈ Δ}.
On appelle chemin une suite c = t1 t2 … tn de transitions ti = (qi, σi, pi) telle que ∀i, ti ∈ Δ et pour 0 < i < n, qi+1 = pi. La longueur du chemin n est notée |c| et son étiquette est la concaténation des lettres étiquetant la suite des transitions : w = σ1 σ2 … σn.
Le langage reconnu par un automate A est défini par :
L(A) = {w ∈ Σ∗ | δ1∗(I , w) ∩ F = ∅}
soit l’ensemble des étiquettes des chemins menant d’un état initial a` au moins un état final.
Les conventions graphiques que nous utiliserons sont les suivantes (figure 2.1) : les tran-sitions sont représentées par des flèches reliant deux états et etiquetées par les lettres de l’alphabet ou par ǫ. Les états initiaux sont représentés par des doubles cercles et les états finaux sont en gris. Sauf absolue nécessité, on omettra la représentation des tags pour des besoins de clarté.
L’automate A a pour alphabet {a, b, c}, pour ensemble d’états {1, 2, 3, 4, 5} avec un état initial 1 et deux états finaux 2 et 5. Il a pour ensemble de transition
Δ = {(1, a, 2), (2, b, 2), (1, b, 3), (3, a, 5), (1, b, 4), (4, c, 5)}
et il reconnaˆıt les mots ba, bc ainsi que les mots commen¸cant par la lettre a suivie d’un nombre quelconque de b éventuellement nul.

Propriétés

Nous utiliserons l’automate A (figure 2.1) de la section 2.2.2 pour illustrer les définitions.

Asynchrone

Un automate est dit asynchrone lorsqu’il possède des ǫ-transitions. Le terme d’asynchrone vient du fait qu’il est possible d’avancer sur l’automate en suivant des ǫ-transitions sans pour autant avancer sur le texte. Pour un automate synchrone, avancer sur une transition signifie obligatoirement qu’il faut lire une lettre dans le texte. L’automate A est synchrone.
Remarque : L’asynchronicité entraˆıne le non déterminisme mais il est toujours possible de supprimer les ǫ-transitions.

Déterministe

Un automate est déterministe si et seulement si :
1. Il possède un unique état initial i.
2. (q, σ, p), (q, σ, p′) ∈ Δ ⇒ p = p′.
3. Il ne contient pas d’ǫ-transition.
Autrement dit, pour tout état q il existe au plus une transition sortante etiquetée par la lettre
σ : |δ1(q, σ)| ≤ 1. De plus, on définit l’état nul, noté 0, comme résultat de la fonction de transition lors d’un échec et dont la définition déterministe est :
δ1 : Q×Σ→Q∪{0}
δ1 (q, σ) = p si (q, σ, p) ∈ Δ
0 sinon
Remarque : Pour tout automate fini A il existe un automate fini B déterministe tel que L(A) = L(B). La preuve ce théorème fait intervenir l’automate des parties de Q [6]. L’auto-mate de la figure 2.2 est l’équivalent déterministe de A (les états 3 et 4 ne forment plus qu’un seul état {3, 4}).

Complet

Un automate est complet lorsque tout état possède au moins une transition étiquetée par chacune des lettres de l’alphabet : ∀q ∈ Q, ∀σ ∈ Σ, δ1(q, σ) = ∅
Remarque : On construit facilement pour tout automate A l’automate complet A′ recon-naissant le mˆeme langage en ajoutant un état « puits »non final vers lequel sont dirigées les transitions sortantes etiquetées par les lettres manquantes (voir figure 2.3 pour le complét´ de A).

Acyclique

Un automate est acyclique lorsque le graphe orient´ sous-jacent ne possède pas de cycle. Pour une définition formelle des cycles sur les graphes voir [6]. A est rendu cyclique par la transition (2, b, 2).
Remarque : les automates acycliques reconnaissent des langages finis.

Minimal

Dans l’ensemble des automates finis reconnaissant un langage L, il en existe un plus pe-tit que tous les autres en terme d’états (à un isomorphisme près). De ce théorème, dont la preuve est basée sur l’équivalence de Nérode, découle l’algorithme classique de minimisation d’Hopcroft (basé sur la construction de Moore, cf [6] pour la preuve détaillée et la construc-tion). Pour la minimisation eﬃcace des automates acycliques voir [54]. Pour une description exhaustive des algorithmes de minimisation on se référera a` [79].
L’automate de la figure 2.2 est minimal (les états 3 et 4 ont été fusionnés, tous les états sont distincts au sens de Nérode).

Langages et expressions rationnels

Définitions

– On appelle opérations rationnelles l’union, le produit et l’étoile.
– Un langage L sur Σ∗ est dit rationnel lorsqu’il peut-ˆetre obtenu de fa¸con finie a` partir de parties finies de Σ∗ grˆace aux opérations rationnelles d’union, de produit et d’étoile.
– La description d’un langage comme une combinaison finie d’opérations rationnelles et de parties finies de Σ∗ a` un elément est une expression rationnelle.

Théorème de Kleene

L est rationnel ⇔ il existe un automate A reconnaissant L
Une preuve de ce théorème fait intervenir pour la partie implication ⇒ les propriétés de fermeture pour les opérations rationnelles des langages reconnus par les automates et pour la partie symétrique ⇐ l’algorithme de MacNaughton et Yamada permettant de construire une expression rationnelle a` partir d’un automate.
Ce théorème est fondamental car il lie directement la définition syntaxique formelle d’un langage (sa spécification rationnelle) a` l’automate le reconnaissant par un algorithme.

Automates déterministes étendus et transitions par défaut

Les automates suivants étendent leur définition de manière a` augmenter le pouvoir ex-pressif des langages reconnus : en définissant des fonctions de transition déterministes δ1 plus elaborées ils permettent l’étiquetage des transitions par des opérations ensemblistes sur Σ. Il en découle le plus souvent, en restant dans le cadre des langages rationnels, des algorithmes plus eﬃcaces et plus clairs notamment pour l’algorithme de recherche de motif d’Aho et Co-rasick [1] et l’implémentation des automates étendus [53].

Automate avec état par défaut

On construit un automate A(Σ, Q, i, F, Δ, s) avec un état par défaut en ajoutant a` la définition déterministe de l’automate un état s ∈ Q et en définissant δ1 par : δ1 (q, σ) = p si (q, σ, p) ∈ Δ s sinon
Remarque : Cette définition de δ1 revient a` adjoindre a` chaque état q de l’automate une transition dirigée vers s etiquetée par Σ \c (q), c’est-a`-dire l’ensemble des lettres qui n’ap-paraissent pas sur les transitions sortant de q. Cette fonction de transition rend A complet de fa¸con économique avec s comme état puits et rend donc l’automate cyclique s’il ne l’était déjà.

Automate avec transitions par défaut

Un automate déterministe avec transitions par défaut A(Σ, Q, i, F, Δ, Δ) o`u Δ ⊆ Q × Q associe a` tout ou partie des états de Q un état p résultat de la fonction de transition lors d’un échec :
p si (q, σ, p) ∈ Δ sinon
δ1(q, σ) = s si (q, s) ∈ Δ sinon

Table des matières

1 Introduction
1.1 Fondements de la programmation générique
1.2 Mise en oeuvre
1.2.1 Principes
1.2.2 Généricité en C++
1.3 Automates génériques
1.4 Domaine
1.5 Au-delà de la programmation générique
1.6 Plan
2 Les automates
2.1 Mots et langages
2.1.1 Définitions
2.1.2 Opérations sur les langages
2.2 Automates finis
2.2.1 Définition
2.2.2 Exemple
2.2.3 Propriétés
2.2.4 Langages et expressions rationnels
2.2.5 Automates déterministes étendus et transitions par défaut
2.2.6 Opérations sur les automates finis
2.3 Automates et parcours
2.3.1 Parcours simple
2.3.2 Parcours en profondeur
2.3.3 Parcours en largeur
3 Les containers ASTL
3.1 Structure générale
3.2 Le concept d’automate
3.2.1 Transitions sortantes
3.2.2 ´ Etats
3.2.3 ´ Etats terminaux
3.2.4 ´ Etats initiaux
3.2.5 Automate
3.3 Concept et modèles d’automate déterministe
3.3.1 Interface et comportement
3.3.2 Modèle matriciel
3.3.3 Modèle compact
3.3.4 Implémentation par map
3.3.5 Implémentation par hachage
3.3.6 Implémentation par listes d’adjacence
3.4 Concept et modèles d’automate non-déterministe
3.4.1 Interface, comportement et types externes
3.4.2 Types internes exportés
3.4.3 Implémentation par multimap
3.4.4 Modèle matriciel
3.5 Conclusion
4 Les curseurs
4.1 Notations
4.2 Motivations
4.3 Le curseur simple
4.3.1 Définition
4.3.2 Propriétés
4.3.3 Comportement et interface
4.3.4 Paramètres d’instanciation
4.3.5 Exemple
4.4 Le curseur monodirectionnel
4.4.1 Définitions
4.4.2 Propriétés
4.4.3 Comportement et interface
4.4.4 Paramètres d’instanciation
4.4.5 Exemple
4.5 Trajectoire
4.6 Le curseur pile
4.6.1 Définition
4.6.2 Propriétés
4.6.3 Comportement et interface
4.6.4 Paramètres d’instanciation
4.7 Le curseur file
4.7.1 Définition
4.7.2 Propriétés
4.7.3 Comportement et interface
4.7.4 Paramètres d’instanciation
4.8 Le curseur de parcours en profondeur générique
4.8.1 Problématique
4.8.2 Définition
4.8.3 Propriétés
4.8.4 Comportement et interface
4.8.5 Paramètres d’instanciation
4.8.6 Exemple
4.9 Automates cycliques et marquage des états
4.10 Conclusion
5 Les adaptateurs
5.1 Définitions
5.2 Les opérations ensemblistes
5.3 Les transitions par défaut
5.4 Construction paresseuse (Lazy Implementation)
5.5 Automates virtuels
5.5.1 Le curseur ∗
5.5.2 L’automate des permutations
5.5.3 Automates isomorphes
5.6 Les algorithmes et leur utilisation
5.6.1 Les fonctions d’aide (helper functions)
5.6.2 appartient
5.6.3 langage
5.6.4 ccopy et clone
5.7 Conclusion
6 Métaprogrammation statique
6.1 Librairies actives et programmation générative
6.1.1 Paradigmes de programmation émergeants
6.1.2 Principes généraux
6.1.3 Mise en oeuvre
6.2 Métaprogrammation statique en C++
6.2.1 Un exemple introductif
6.2.2 Les métafonctions
6.2.3 La fonction d’aide dfirstc
6.3 Vers une librairie active de machines à états
6.3.1 Domaine
6.3.2 Concepts
6.3.3 Définitions
6.4 Le DSL « machine à état »
6.4.1 Grammaire
6.4.2 Le container de transitions
6.4.3 Le type de tag
6.4.4 L’optimisation
6.4.5 L’orientation des arcs
6.4.6 Les états terminaux
6.4.7 Les états initiaux
6.4.8 Vérification des opérations
6.4.9 Exemple d’utilisation
6.4.10 Valeurs par défaut des paramètres du DSL
6.5 ICCL « machine à états »
6.5.1 Grammaire
6.5.2 Principes d’implémentation
6.5.3 Interface du concept FSM
6.6 Projection du DSL vers l’ICCL
6.6.1 Mécanique
6.6.2 Exemple
8 TABLE DES MATI` ERES
6.6.3 L’interface externe « FSM Wrapper »
6.7 Le générateur de curseurs
6.8 Conclusion
7 Conclusion
Documentation de référence
A.1 Concepts
A.2 Modèles
A.3 Algorithmes