Théorie des langages/Définitions

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

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 $\mathrm{\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é $ϵ$ (ou parfois aussi $\mathrm{\Lambda }$)

Définitions

Les mots

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

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

On note ${\mathrm{\Sigma }}^{*}$ l’ensemble des mots sur $\mathrm{\Sigma }$, et ${\mathrm{\Sigma }}^{+}$ l’ensemble des mots autres que $ϵ$

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

La concaténation des mots

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