Grammaires de mots et langages

Grammaires de mots et langages

Mots et langages

Nous considérons des ensembles finis de symboles, ou lettres, appelés alphabets. Les suites finies de lettres sont appelées mots. Autrement dit, un mot u de longeur n ≥ 0 sur un alphabet Σ peut être vu comme un n-uplet (a1, · · · ,an) d’éléments de Σ, ou de façon équivalente comme une application de l’intervalle des entiers [1,n] dans Σ. Tout mot u = (a1, · · · ,an) est habituellement noté a1 · · · an ; sa i-ème lettre est u(i) = ai . L’ensemble de tous les mots construits sur Σ se note Σ∗ . Un langage sur l’alphabet Σ est un sous-ensemble de Σ∗ .

Le nombre d’occurrences d’une lettre a dans un mot u est noté |u|a. Ainsi, le nombre total d’occurrences de toutes les lettres dans le mot u est sa longueur et se note |u|. L’unique mot de longueur 0, qui ne contient aucune lettre, est appelé le mot vide et est noté ε.

La concaténation de deux mots u = a1 · · · an et v = b1 · · · bm, qui se note u.v ou plus simplement uv, est le mot uv = a1 · · · anb1 · · · bm. Ainsi, la concaténation est une opération associative ayant ǫ pour élément neutre. Pour tout mot u = xvy, v est un facteur de u, x est un préfixe de u et y est un suffixe de u. En particulier, tout préfixe ou suffixe d’un mot est un facteur du mot.

L’itération de la concaténation à tout langage L est : L∗ = S n≥0 L n , avec L0 = {ε} et L n+1 = Ln .L pour tout n ≥ 0.

De façon abusive, on pourra écrire u à la place de {u}. Ainsi Σn est l’ensemble des mots de longueur n.

Exemple. Avec un alphabet Σ = {0, 1}, nous avons :

Σ∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000, 001, · · · }
(11000)0 = ε
(110)² = 110110
1³ = 111

Monoïdes. La structure algébrique sous-jacente aux mots est le monoïde. Un monoïde M est simplement un ensemble, potentiellement infini, muni d’une opération interne associative appelée produit, et d’un élément neutre 1M. Une partie S d’un monoïde M est un ensemble de générateurs de M si chaque élément de M admet une décomposition comme produit d’éléments de S : M = S∗ ; on dit que S est libre si toute décomposition en éléments de S est unique :

Si u1 · · · um = v1 · · · vn avec u1, · · · ,um,v1, · · · ,vn ∈ S
alors m = n et u1 = v1, · · · ,un = vn.
Si de plus S est fini, M est dit de type fini.

Exemple. L’ensemble N des entiers positifs est un monoïde pour l’addition. Son élément neutre est 0. Il est librement engendré par le singleton {1} et est donc de type fini.

Exemple. L’ensemble Σ∗ de tous les mots sur un alphabet Σ est un monoïde pour la concaténation. Il est de type fini et librement engendré par Σ. Son élément neutre est le mot vide ε.

Systèmes de récriture

Les systèmes de récriture figurent parmi les formalismes les plus simples et les plus généraux pour la modélisation de transformations sur les mots (voir par exemple [DJ 90] et [Ca 90]). Ils généralisent les grammaires, peuvent représenter des calculs d’automates finis, de transducteurs, d’automates à pile ou même de machines de Turing. Autant que faire se peut, nous donnerons une caractérisation de chacun de ces formalismes en termes de systèmes de récriture

Un système de récriture de mots sur l’alphabet Σ est un ensemble potentiellement infini de règles de récriture, c’est-à-dire de couples de mots (l,r) ∈ Σ∗ × Σ∗ .

Exemple. Un système de récriture sur l’alphabet Σ = {0, 1,S} est le suivant :

R = {(S, 0S),(S, 1S),(S, 0),(S, 1)}

Ce qui s’écrit de la façon plus lisible suivante :

S → 0S
S → 1S
S → 0
S → 1

Table des matières

1 Introduction
2 Notions préliminaires
2.1 Grammaires de mots et langages
2.1.1 Mots et langages
2.1.2 Systèmes de récriture
2.1.3 Grammaires et hiérarchie de langages
2.2 Grammaires de graphes et langages
2.2.1 Graphes
2.2.2 Chemins
2.2.3 Graphes et langages
2.2.4 Isomorphisme de graphes
2.2.5 Grammaires de graphes
3 Grammaires de graphes et langages algébriques
3.1 Lemme des paires itérantes
3.1.1 Introduction
3.1.2 Lemme des paires itérantes
3.1.3 Démonstration géométrique du lemme des paires itérantes
3.2 Lemme de Parikh
3.2.1 Introduction
3.2.2 Lemme de Parikh
3.2.3 Démonstration géométrique du lemme de Parikh
4 Plus courts chemins
4.1 Calculs avec des grammaires de graphes
4.2 Algorithmes de calculs
4.3 Calculs sur des graphes réguliers
5 Régularité et algébricité des systèmes de récriture
5.1 Introduction
5.2 Décomposition de la dérivation
5.2.1 Notations
5.2.2 Propriétés de préservation
5.2.3 Décomposition
5.3 Applications
5.3.1 Systèmes préfixes, suffixes et bifixes
5.3.2 Dérivation gauche-droite
5.3.3 Systèmes marqués
6 Conclusion

Lire le rapport complet