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

{{Chapitre
  | idfaculté = informatique
  | numéro    = 2
  | précédent = [[../Introduction/]]
  | suivant   = [[../Machine de Turing/]]
  | niveau    = 17
}}

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

Exemple :

<math>\Sigma = \{a,b\}</math> et <math>\Sigma^* = \{ e , a, b, aa, ab, ba, bb, aaa, \dots \}</math>

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

Un automate tel que :

:[[Fichier:Calculabilité et complexité - automate.png]]

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

Un langage tel que <math>L = \{ a^n b^n | n \in \N\}</math> n’est pas reconnaissable d'un automate, c’est ce qu'énonce le [[w:Lemme de l'étoile|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 <math>L = \{ a^n b^n c^n| n \in \N\}</math> n’est pas algébrique, c’est ce qu'énonce le [[w:Lemme de la double étoile|Lemme de la double étoile]].

Puis on a les [[w:Langage récursif|langages récursifs]].


{{Bas de page
  | idfaculté = informatique
  | précédent = [[../Introduction/]]
  | suivant   = [[../Machine de Turing/]]
}}