3. Mots et monoïdes libres

Intuitivement, un mot est un ensemble de symboles d'un alphabet placés les uns après les autres donc une suite de lettres (ou chaîne de caractères, dans une terminologie plus informatique).

Remarque : Dans la suite, les alphabets seront décrits comme des ensembles de symboles (entre accolades), éventuellement composés de plusieurs caractères. Les symboles représentés par des signes de ponctuation seront entre quotes.

Par exemple, A₁ = {1}, A₂ = {0, 1}, A₃ = {., -, /}, A₄ = {0, 1, 2, ..., 9}, A₅ = {a, b, ..., z}, A₆={a,b,ch,';',','} et A={a,b,c} sont des alphabets et abbc, aaaa, bc, ε sont des mots sur l'alphabet A, respectivement de longueur 4, 4, 2 et 0.

Soit l'alphabet {a,b,c,h,ch,';',','}. Les mots ch (|ch|=1) et c ⊕ h ≡ ch (|c ⊕ h|=2) sont théoriquement différents. Il n'y a donc (théoriquement) pas d'ambiguïté sur le mot ch. En pratique, cette ambiguïté est à lever. Dans le suite de ce cours, nous prendrons volontairement des alphabets qui ne présenterons pas cette ambiguïté.

Par convention (valable dans la suite du document), nous posons :

• Que a, b, c, d, e, f, 0, 1... désignent des symboles.
• Que t, u, v, x, y, z désignent des chaînes.
• La chaîne aaaa est aussi notée a⁴. Par conséquent, a⁰=ε.
• Le symbole m(i) désigne le i-ème symbole de la chaîne m.

Dans la suite, nous définissons les mots comme les éléments de monoïdes particuliers. On peut définir sur les mots (ou chaînes) une opération particulière : la concaténation. Intuitivement, si x et y sont des chaînes, alors le résultat de la concaténation de x et y est la chaîne xy. Cette opération est associative : (xy)z=x(yz)=xyz (Les parenthèses sont ici des symboles mathématiques et n'appartiennent pas à l'alphabet de référence). De plus, la chaîne vide ε est un élément neutre pour la concaténation. L'ensemble des mots sur un alphabet donné peut ainsi être muni d'une structure de monoïde . Ce type de monoïde, un peu particulier, est appelé monoïde libre.

Par exemple, si x=ab et y=cd, alors x ⊕ y = xy = abcd. De plus, x ⊕ ε = ε ⊕ x = x et, par exemple, (ab ⊕ cd) ⊕ ef = abcd ⊕ ef = abcdef = ab ⊕ (cdef) = ab ⊕ (cd ⊕ ef).

Remarques :

• L'ensemble A^* des mots ainsi construit est infini dénombrable.
• Les symboles de l'alphabet sont atomiques, ie : si a ∈ A, ∀ x,y ∈ A⁺ : a ≠ xy
• Il n'y a pas d'inverse pour l'opération de concaténation, ie : si u ∈ A⁺, ∀ v ∈ A⁺ : uv ≠ ε

Ce théorème sert de base à beaucoup de démonstrations par induction sur la longueur des mots.

Par exemple, avec A = {a,b,c} alors abbcabbc = a ⊕ b ⊕ b ⊕ c ⊕ a ⊕ b ⊕ b ⊕ c.

Remarque : Une chaîne sur un alphabet A peut également être définie récursivement par :

• la chaîne vide ε est une chaîne sur A;
• si x est une chaîne sur A et a ∈ A alors la chaîne ax et xa sont des chaînes (mots) sur A (Attention, dans le cas général, ax ≠ xa);
• aucun autre objet n'est une chaîne sur A.

Cette définition sert de base pour la démonstration de nombreuses propriétés à propos des mots, par récurrence (induction) sur leur longueur. L'idée générale est que pour montrer qu'une propriété P est vraie pour tous les mots, il suffit de montrer que P est vraie pour ε (cas de base) et que si P est vraie pour un mot x (hypothèse de récurrence), alors elle est vraie pour ax, ∀ a.

Notations :

• L'ensemble des mots (ou chaînes) de longueur n (pour n ∈ N) construits sur A est noté Aⁿ (Aⁿ = {x₁x₂...x_n | ∀ i, 1 ≤ i ≤ n, x_i ∈ A}) . Par conséquent, toutes les chaînes y de l'ensemble A³ ont pour longueur |y|=3.
• L'ensemble des chaînes de longueur finie et non nulle définies sur A est noté A⁺= ∪_n=1..∞ Aⁿ ={x | ∃n ∈ N, n ≥ 1 et x ∈ Aⁿ}.
  Notons que A* = A⁺ ∪ {ε}
• Par convention, A⁰ est ε et donc A*=∪_n=0..∞ Aⁿ

Par exemple, si l'on considère l'alphabet A= {0,1} alors :

• A⁰={ε} ;
• A¹ = A ={0, 1} ;
• A² = {0,1}² = {00, 01, 10, 11} ;
• A³ = {0,1}³ = {000, 001, 010, 011, 100, 101, 110, 111};
• ...
• A^* = {0,1}^* = {ε, 0,1, 00,01,10, 11,000, 001, 010, 011,..., 11111, ..., 1001101110...}.
• A⁺ = {0,1}⁺ = {0,1, 00,01,10, 11,000, 001, 010, 011,..., 11111, ..., 1001101110...}.
• si S = {ε,0, 00, 000, 0000, ...} = {0ⁱ} ⊂ A⁺ (avec ε=0⁰) alors <S,⊕,ε> est le sous-monoïde de <A^*,⊕,ε> engendré par {0}.

Remarque : Si c₁ ∈ Aⁿ et c₂ ∈ A^m alors c₁ ⊕ c₂ ∈ A^n+m.

jeudi, 11/12/03 11:00