Théorie des langages/Définitions

Début de la boite de navigation du chapitre

Vous trouverez dans ce chapitre les notations et définitions permettant de travailler sur les langages par la suite

fin de la boite de navigation du chapitre

Notations

• La concaténation de deux caractères a et b se note $a.b$, ou par abus de notation $ab$
• La répétition d'un caractère a, n fois se note $a^{n},n\in \mathbb {N}$
• La répétition d'un caractère un nombre quelconque de fois entre 0 et $\infty$ se note $a^{*}$
• La répétition d'un caractère un nombre quelconque de fois strictement positif se note $a^{+}$
• Le mot vide (sans aucune lettre) est noté $\epsilon$ (ou parfois aussi $\Lambda$)

Début de l'exemple

Exemple

• L'expression $ab^{*}a$ peut correspondre aux mots : aa, aba, abba, ...
• L'expression $aa^{*}$ est équivalente à $a^{+}$

Fin de l'exemple

Définitions

Les mots

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 $\epsilon$ est un mot sur $\Sigma$
• Si $a\in \Sigma$, et ω 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$

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

Définition : longueur d'un mot

La longueur d'un mot ω 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 mots

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}$