Structures algébriques et langages

Structures algébriques et langages

Monoïdes et semi-anneaux Monoïdes

Un monoïde est un ensemble M muni d’une loi binaire associative, que l’on appellera généralement multiplication, et d’un (unique) élément neutre que l’on notera 1M. Un monoïde qui ne dispose pas d’un élément neutre est appelé un semigroupe. La multiplication est notée avec un point : p · q ou simplement pq s’il n’y a pas de risque d’ambiguïté. Lorsque l’on voudra spécifier une certaine opération de multiplication ⊗ pour un monoïde M, on désignera le monoïde par (M, ⊗). Si cette dernière est commutative, on dit que le monoïde est commutatif et on appellera en général cette opération l’addition.

S’il existe  un élément z tel que pour tout élément m de M on a zm = mz = z, on dit que z est absorbant, on l’appellera le zéro du monoïde et on le notera 0M. REMARQUE 2.1 Il est toujours possible de munir un semigroupe d’un élément neutre et donc d’en faire un monoïde. De ce fait, s’il s’avère que la structure de base est un semigroupe, on la transformera implicitement en monoïde pour ne manipuler que ce type de structure.

Étant donné que les axiomes de monoïde sont relativement faibles, tous les groupes sont des monoïdes de même que la plupart des ensembles classiques munis d’une loi qui vérifie ces axiomes, en voici quelques exemples : i ) (N, +), l’ensemble des entiers naturels muni de l’addition avec 0 pour élément neutre. ii ) (N, max), l’ensemble des entiers naturels muni de la loi M ax (qui à deux entiers associe le plus grand des deux) avec 0 pour élément neutre. iii ) (Z, ∗), l’ensemble des entiers relatifs muni de la multiplication avec 1 pour élément neutre (et 0 comme élément absorbant). iv ) (P(E), ∪), l’ensemble des partie d’un ensemble E muni de l’union ensembliste avec l’ensemble vide pour élément neutre. v ) (A∗ , .), l’ensemble des mots sur l’alphabet A avec l’opération de concaténation et avec le mot vide pour élément neutre

Ensembles reconnaissables et ensembles rationnels

Dans la suite, nous ferons coïncider deux types d’ensembles, les parties reconnaissables et les parties rationnelles. Il s’agit d’un théorème extrêmement important, le théorème de Kleene dont on rappellera les détails dans la suite. Pour le moment, nous allons nous intéresser aux concepts généraux de reconnaissabilité et de rationalité. Définition 2.13 Un sous-ensemble L d’un monoïde M est reconnu par un monoïde N s’il existe un morphisme (surjectif) ϕ de M dans N et un sous ensemble P de N tels que L = ϕ −1 (P) (ou, autrement dit, si L est l’image  inverse par ϕ d’une partie de N).

Si N est un monoïde fini, alors L est un sous-ensemble reconnaissable de M. Une autre façon de voir les choses est de dire que L est une partie reconnaissable de M si elle est saturée par une congruence d’index fini. On note Rec M l’ensemble des parties reconnaissables de M.

EXEMPLE 2.9

Soit S le semi groupe défini sur {0, 1, 2} par x+y = min(x+ y, 2) et soit ϕ un morphisme (surjectif) de (N, +) dans S défini par ϕ(0) = 0, ϕ(1) = 1 et ϕ(n) = 2 quel que soit n > 1. Alors les ensembles reconnaissables de N par ϕ sont ϕ −1 (∅) = ∅, ϕ −1 (0) = {0}, ϕ −1 (1) = {1}, ϕ −1 (2) = {2, 3, . . .}, ϕ −1 ({0, 1}) = {0, 1}, ϕ −1 ({0, 2}) = {0, 2, 3, . . .}, ϕ −1 ({1, 2}) = {1, 2, 3, . . .} et ϕ −1 ({1, 2, 3}) = N