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. Pour tout n ∈ N, le mot u n est la concaténation n fois du mot u et est défini par récurrence de la façon suivante : u 0 = ǫ u n = u n−1 .u pour tout n > 0. L’opération de concaténation s’étend aux langages : pour tout A,B ⊆ Σ ∗ , AB = { uv | u ∈ A ∧ v ∈ B }. L’itération de la concaténation à tout langage L est : L ∗ = S n≥0 L n , avec L 0 = {ǫ} et L n+1 = L n .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)2 = 110110 1 3 = 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. 10 2.1. Grammaires de mots et langages 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 On note Dom(R) (resp. Im(R)) l’ensemble des parties gauches (récipoquement droites) des règles de R. Une règle (l,r) récrit un mot w en w ′ en remplaçant une instance de l dans w par r. Plus formellement, la relation de récriture d’un système R est : −→R := { (ulv,urv) | (l,r) ∈ R ∧ u,v ∈ Σ ∗ }. La clôture réflexive et transitive de cette relation pour la composition est la dérivation de R et est notée habituellement ∗ −→ R . Pour tout u, v tels que u ∗ −→ R v, il existe une suite de mots u0, · · · ,un telle que : u = u0 −→R u1 · · · un−1 −→R un = v. Nous disons que v est dérivable de u ou bien que u se dérive en v. 11 Chapitre 2. Notions préliminaires Un mot w ne contenant aucune instance de partie gauche de règle d’un système R est appelé une forme normale (ou forme irréductible) de R. Un système de récriture pour lequel tout mot w peut être dérivé en une forme normale est appelé normalisant, et fortement normalisant si cette forme normale est unique pour tout mot donné.

Grammaires et hiérarchie de langages

Dans cette partie, nous donnons quelques rappels sur la hiérarchie la plus connue de la théorie des langages formels, à savoir la hiérarchie de familles de langages dite de Chomsky [Ch 59]. Définie il y a plus de cinquante ans, elle est formée des quatre familles décroissantes des langages suivants : les langages récursivement énumérables, les langages contextuels, les langages algébriques et les langages réguliers. Cette partie rappelle les quatre classes de grammaires utilisées pour définir les familles de la hiérarchie de Chomsky. La hiérarchie de Chomsky fut initialement définie en termes de grammaires qui sont des cas particuliers de systèmes de récriture de mots, et ce dans le but de fournir des outils pour l’étude de langues naturelles. Une grammaire G est caractérisée par un quadruplet G = (T,N,S,P) où T et N sont deux alphabets finis disjoints et (i) T est l’alphabet de symboles terminaux de la grammaire ; T est appelé l’alphabet terminal, (ii) N est l’alphabet de symboles non-terminaux ou symboles variables de la grammaire ; N est appelé l’alphabet non-terminal, (iii) S ∈ N est le symbole initial appelé axiome ou racine de la grammaire, (iv) P est un système de récriture de mots sur l’alphabet T ∪ N, dont les éléments sont en général appelés les règles de la grammaire. Pour plus de simplicité, on requiert en général que les parties gauches des règles de P contiennent au moins un symbole non-terminal. On dit qu’un mot u ∈ T ∗ est engendré par G s’il peut être dérivé depuis l’axiome S selon le système P. Le langage de la grammaire G est défini comme l’ensemble de tous les mots terminaux (dans T ∗ ) qui sont engendrés par G : L(G) = { u ∈ T ∗ | S ∗ −→ P u }. Remarque. Par définition des règles de la grammaire, un mot ne contenant que des symboles terminaux ne peut plus se récrire ; il s’agit d’une forme normale pour le système de récriture P. Le fait de distinguer explicitement les symboles terminaux des non-terminaux n’est pas une caractéristique essentielle des grammaires, qui peuvent en fait être vues simplement comme des systèmes de récriture.