Calculabilité et complexité/Rappel sur la notion de langage

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

On note $\Sigma$ un alphabet et $\Sigma ^{*}$ un ensemble de mots, c'est-à-dire de suites finies composés avec les lettres de $\Sigma$. On note également $e$ le mot vide, c'est-à-dire le mot composé d'aucune lettres.

Exemple :

$\Sigma =\{a,b\}$ et $\Sigma ^{*}=\{e,a,b,aa,ab,ba,bb,aaa,\dots \}$

Un langage est un sous-ensemble de $\Sigma ^{*}$. Par exemple avec $\Sigma =\{a,b\}$ on a $L=\{w\in \Sigma ^{*}|w{\text{ contient au moins un }}a\}$.

Un automate tel que :

permet de construire des chaîne comme « bbabaa ».

Un langage tel que $L=\{a^{n}b^{n}|n\in \mathbb {N} \}$ n’est pas reconnaissable d'un automate, c’est ce qu'énonce le Lemme de l'étoile.

Un langage reconnaissable avec un automate est dit rationnel.

Un automate à piles permet de reconnaître un langage algébrique.

Un langage tel que $L=\{a^{n}b^{n}c^{n}|n\in \mathbb {N} \}$ n’est pas algébrique, c’est ce qu'énonce le Lemme de la double étoile.

Puis on a les langages récursifs.