Les mots sont une structure très utilisée en informatique. La théorie des langages classifie les ensembles de mots (langages réguliers ou algébriques) suivant leur propriétés, en particulier la manière de reconnaître qu’un mot appartient à un certain langage. Un programme donné à interpréter à un ordinateur est un mot. De la même manière, on peut représenter les actions réalisées par un programme par un mot, et donc certaines techniques d’analyse de programme s’appuient sur des résultats de théorie des langages.
Les mots sont aussi la notion sous-jacente aux structures séquentielles (tableaux, listes) qui servent dans de nombreux algorithmes en particulier pour représenter en machine des ensembles d’objets.
On se donne un ensemble (en général fini) d’objets A que l’on appelle un alphabet. Les éléments d’un alphabet sont appelés des caractères.
Les mots sont des suites finies de caractères. On peut les représenter comme des couples formés d’un entier n (la taille du mot) et d’une application f de [0,n[ dans A. On notera A* l’ensemble des mots sur l’alphabet A.
Si m est un mot, on note |m| la longueur du mot et pour chaque i < |m|, on note m[i] le i-ème caractère du mot m (on commence à 0).
Pour définir un mot m, il suffit de se donner sa longueur n et une application de [0,n[ dans A.
On introduit les opérations suivantes sur les mots:
On montre les propriétés essentielles des opérations précédentes.
Un mot m qui n’est pas vide a un premier caractère a=m[0] et peut être décomposé m=am′ avec m′ le mot obtenu en retirant le premier caractère de m et défini par : |m′|=|m|−1 et m′[i]=m[i+1]. On introduit les notations hd(m) pour le caractère a et tl(m) pour le mot m′.
Un langage est un ensemble de mots. Il peut se définir par un système d’inférence.
|
|
|
aabb abb aab abab |
|
|
Le schéma de définition récursive sur les entiers se généralise au cas des mots. Une manière naturelle de définir une application f dans A*→ B consiste à définir la valeur b∈ B de l’application pour le mot vide, et pour un caractère a ∈ A arbitraire et un mot m∈ A* de définir f(am) en fonction de a, de m et de f(m), c’est-à-dire se donner une application G dans A× A* × B → B telle que f(am)=G(a,m,f(m)).
lg(є)=0 lg(am)=1+lg(m) |
nb(b,є)=0 nb(b,am)=1+nb(b,m) si a=b nb(b,am)=nb(b,m) si a≠ b |
On remarque que l’on ne peut pas se servir de la concaténation de deux mots arbitraires comme construction d’équations fonctionnelles. En effet si on pose des équations:
f(є)=0 f(a)=1 f(m1 m2)=1+f(m1)+f(m2) |
alors ces équations n’ont pas de solution en effet on devrait avoir f(aє)=1+f(a)+f(є)=2 et par ailleurs comme aє=a, on a aussi f(aє)=f(a)=1 ce qui ne peut se réaliser. On peut toujours utiliser une définition par cloture de la relation f(x,n) mais cette relation n’est pas fonctionnelle. Cela vient du fait que la décomposition d’un mot m sous la forme m1m2 n’est pas unique.
Nous allons généraliser les constructions introduites précédemment pour les entiers ou les mots à des structures plus complexes. En effet en informatique, la machine manipule in fine des données assez simples à savoir des suites (finies) de 0 et de 1. Néanmoins, lorsqu’on veut modéliser une structure particulière comme une base de données ou une image, ces suites de 0 et de 1 sont organisées suivant des schémas très spécifiques. L’identification de ces schémas va nous permettre d’avoir des moyens de haut niveau pour construire ces objets et raisonner en faisant abstraction de la représentation physique.
On est amené par exemple à manipuler des structures d’arbres, que ce soit des arbres binaires pour représenter efficacement des ensembles finis d’objets ou bien des arbres de syntaxe abstraite pour représenter des programmes dans les compilateurs.
Dans cette section, on s’intéresse à des représentations syntaxiques, qu’il faut bien distinguer du modèle sous-jacent. Par exemple si on considère l’expression 2+3, le niveau syntaxique fait une différence entre cette expression et les expressions 5, 3+2 ou 2+(2+1) alors que toutes ces expressions correspondent au même modèle entier 5. Cette distinction entre syntaxe et modèle réel est importante en informatique où l’ordinateur effectue des manipulations symboliques sur des objets structurés qui représentent des notions complexes (des nombres flottants voir des rationnels ou des réels, des bases de données, des programmes, …).
|
|
On utilise parfois une notation infixe pour les symboles de fonctions binaires, c’est-à-dire que l’on écrira (t1 f t2) au lieu de f(t1,t2) de même on peut omettre certaines parenthèses en s’appuyant sur des conventions, mais il s’agit de facilités d’écriture qui ne changent pas la définition mathématique.
En logique ou en informatique on a souvent besoin de considérer des termes généralisés dans lesquels apparaissent des variables. On l’a vu avec les formules quantifiées en logique. En informatique, les fonctions dans les langages de programmation correspondent à des termes avec des variables (pour les paramètres). Contrairement aux constantes dans les signatures, les variables peuvent être choisies dans un ensemble infini X (mais seulement un nombre fini de variables apparait dans chaque terme).
|
|
|
Les termes de T( F) sont un cas particulier de terme avec variables dans lesquels l’ensemble des variables X est vide. Dans la suite, on considèrera uniquement des termes sans variables.
L’égalité sur les mots induit une égalité sur les termes. En particulier on peut dériver la propriété suivante :
t=u ⇔ |
|
On peut généraliser la notion de définition récursive d’une application sur les entiers en définition récursive sur des termes arbitraires.
On suppose que l’on veut définir une application F dans T( F) → A. Pour cela on va se donner les objets suivants :
| × |
| → A |
Il existe une unique application F dans T( F) → A qui vérifie :
F(c)=dc (c∈ F0) F(f(t1,…,tn))=Gf(t1,…,tn,F(t1),…,F(tn)) (f∈ Fn) |
Le fait que l’on puisse définir une telle application est une conséquence de l’égalité sur les termes. En particulier, deux termes qui débutent par des symboles différents sont différents.
En effet ce schéma permet de définir une application f telle que f(c)=1 pour les constantes et f(t)=2 pour tous les termes qui commencent par un symbole de fonction. Si on avait plus(0,0)=0 alors on en déduirait f(plus(0,0))=f(0) et donc 2=1.
L’induction généralisée associée à la définition par cloture de T( F) s’exprime de la manière suivante. Soit P(t) une propriété qui dépend d’un terme t ∈ T( F). On suppose :
alors ∀ t ∈ T( F),P(t).
∀ t ∈ T( F),ht(t) ≤ size(t) |
ht(f(t1,…,tn))= |
|
Nous avons défini les termes comme des mots en mettant en avant la structure séquentielle ce qui nous a amené à introduire les symboles parenthèses et virgule. La définition par cloture met l’accent sur la structure arborescente des termes. Une constante est vue comme une feuille de l’arbre, un terme f(t1,…,tn) est représenté comme un arbre dont la racine est étiquetée par f et qui a n fils, que l’on considère de manière ordonnée. Le i-ème sous-arbre est associé au terme ti.
Un terme définit un ensemble de positions. Une position est une suite finie d’entiers compris entre 1 et l’arité maximale des éléments de la signature. La position décrit un chemin pour se déplacer dans l’arbre en partant de la racine, l’entier permet de choisir dans quel sous-terme continuer.
|
|
On remarque que lorsque t est une constante alors: pos(t)={є }.
t|є=t f(t1,…,tn)|im=ti|m |
Lorsque l’on introduit des signatures complexes, il est souvent naturel de distinguer différentes catégories de termes.
Par exemple les termes correspondant aux suites finies peuvent se construire avec une constante nil et un symbole cons binaire pour ajouter un caractère en premier élément d’une suite. Il nous reste à introduire une signature pour représenter les éléments de la suite, par exemple des entiers avec une constante 0 et un symbole unaire S. Dans le cadre général, rien n’interdit de construire des termes comme S(cons(0,є)) qui n’ont pas d’interprétation naturelle.
Pour remédier à ce problème, on introduit des sortes qui permettent de distinguer les différentes classes de termes. Les sortes sont un ensemble fini (par exemple {nat,seq } pour représenter la sorte des entiers naturels et celle des séquences d’entiers). Au lieu d’être un simple entier décrivant le nombre d’arguments, une arité décrit la sorte des termes que le symbole prend en argument et la sorte du terme construit en résultat, on l’écrira s1×…× sn → s. Dans notre exemple de suite d’entiers :
On définit maintenant par cloture l’ensemble T( F,s) des termes de sorte s:
|
Une structure importante en informatique est celle d’arbre binaire. On suppose que l’on souhaite stocker dans cet arbre des objets. On introduit une sorte elt pour représenter ce qui est stocké dans l’arbre avec par exemples des constantes a, b, c, d, e. On introduit également la sorte tree pour les arbres binaires.
Une signature (notée A) possible est donnée par :
L’arbre
est représenté par le terme :
node(node(node(leaf,c,leaf), b, node(leaf,d,leaf) ,a,node(leaf,e,node(leaf,c,leaf))))
qui lui même peut se représenter sous forme d’arbre :
On définit de nombreuses fonctions sur les arbres en suivant le schéma de définition récursive sur les termes.
Par exemple la hauteur:
ht(leaf) = 0 ht(node(l,a,r)) = 1 + max(ht(l),ht(r)) |
On peut aussi définir un parcours d’arbre qui construit la suite finie des éléments qui apparaissent dans l’arbre :
elts(leaf) = є elts(node(l,a,r)) = elts(l) a elts(r) |
De manière générale, le principe de définition récursive sur les arbres est donné par la définition suivante :
Soit une fonction h∈ X → Y et g∈ T × E × T × Y × Y × X → Y alors il existe une unique fonction f∈ T × X → Y telle que :
f(leaf,x)=h(x) f(node(l,e,r),x)=g(l,e,r,f(l,x),f(r,x)) |
De plus la propriété suivante (schéma d’induction sur les arbres) est vérifiée pour toute propriété P sur les arbres :
Comme précédemment, le schéma peut être généralisé en autorisant dans les appels récursifs de f(l,x) et f(r,x) d’appliquer une transformation à x.
Preuve: La fonction demandée est la solution des équations :
sum(leaf)=0 sum(node(l,e,r))=sum(l)+e+sum(r) |
□