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

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

Exemple :

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

Un langage est un sous-ensemble de ${\mathrm{\Sigma }}^{*}$. Par exemple avec $\mathrm{\Sigma }=\{a,b\}$ on a $L=\{w\in {\mathrm{\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.

Modèle:Bas de page