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

Definitions

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

Définition

Alphabet : Ensemble $\Sigma$ fini non vide dont les élémentssont 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 $\epsilon$ est un mot sur $\Sigma$
• Si $a\in \Sigma$, et $\omega$ un mot sur $\Sigma$, alors $a.\omega$ est un mot sur $\Sigma$

On note $\Sigma ^{*}$ l'ensemble des mots sur $\Sigma$, et $\Sigma ^{+}$ l'ensemble des mots autres que $\epsilon$

Lorque l'on travaille avec les mots, plusieurs choses sont à définir

Définition

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

• $|\epsilon |=0|$
• si $\omega =a.\omega '$ avec $a\in \Sigma ,\omega '\in \Sigma ^{*}$, alors $|\omega |=1+|\omega '|$

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 :

• $\epsilon .\omega =\omega$
• si $\omega '=a.u$ avec $a\in \Sigma$ et u un mot sur $\Sigma$, alors $\forall \omega \in \Sigma ^{*},\omega '.\omega =(a.u).\omega =a.(u.\omega )$

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

Définition

• Préfixe : $u\in \Sigma ^{*}$ est un préfixe de $v\in \Sigma ^{*}$ si $\exists w\in \Sigma ^{*},v=u.w$
• Suffixe : $u\in \Sigma ^{*}$ est un suffixe de $v\in \Sigma ^{*}$ si $\exists w\in \Sigma ^{*},v=w.u$
• Facteur : $u\in \Sigma ^{*}$ est un facteur de $v\in \Sigma ^{*}$ si $\exists w_{1},w_{2}\in \Sigma ^{*},v=w_{1}.u.w_{2}$