Théorie des langages/Les mots

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Les mots

Dans ce chapitres nous étudierons les mots, qui sont à la base des langages qu’ils soient formels ou naturels. Nous y verront les définitions et propriétés importantes qui nous permettront de travailler par la suite

Définitions

La structure de base d'un langage est un alphabet.

Définition

Alphabet : Ensemble $\Sigma$ fini non vide dont les éléments sont appelés lettres ou caractères

La structure supérieure à l'alphabet sont les mots, définis comme suit.

Définition

Mot : l’ensemble des mots sur un alphabet $\Sigma$ est défini récursivement de la manière suivante :

• le mot vide $\varepsilon$ est un mot sur $\Sigma$
• Si $a\in \Sigma$, et $w$ un mot sur $\Sigma$, alors $a\cdot w$ est un mot sur $\Sigma$

Remarque

Il est usuel de ne pas marquer le point $\cdot$, et donc d'écrire $aw$ au lieu de $a\cdot w$

On note $\Sigma ^{*}$ l’ensemble des mots sur $\Sigma$, et $\Sigma ^{+}$ l’ensemble des mots autres que le mot vide $\varepsilon$

Lorsque l’on travaille avec les mots, plusieurs choses sont à définir

Définition

Longueur d'un mot : la longueur d'un mot $w$ est notée $|w|$ et est définie récursivement comme suit :

• $|\varepsilon |=0$
• si $w=aw'$ avec $a\in \Sigma ,w'\in \Sigma ^{*}$, alors $|w|=1+|w'|$

La concaténation des mots

Définition

Concaténation de mots : on étend la concaténation de deux caractères à des mots, définie par :

• $\varepsilon \cdot w=w$
• si $w'=au$ avec $a\in \Sigma$ et $u$ un mot sur $\Sigma$, alors $\forall w\in \Sigma ^{*},w'w==a(uw)$

Les définitions suivantes permettent de travailler sur une partie des mots

Définition

• Préfixe : $u\in \Sigma ^{*}$ est un préfixe de $v\in \Sigma ^{*}$ s'il existe $w\in \Sigma ^{*}$ tel que $v=uw$ ;
• Suffixe : $u\in \Sigma ^{*}$ est un suffixe de $v\in \Sigma ^{*}$ s'il existe $w\in \Sigma ^{*}$ tel que $v=wu$ ;
• Facteur : $u\in \Sigma ^{*}$ est un facteur de $v\in \Sigma ^{*}$ s'il existe $w_{1},w_{2}\in \Sigma ^{*}$ tels que $v=w_{1}uw_{2}$ .