Aller au contenu

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

Leçons de niveau 17
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Rappel sur la notion de langage
Icône de la faculté
Chapitre no 2
Leçon : Calculabilité et complexité
Chap. préc. :Introduction
Chap. suiv. :Machine de Turing
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Calculabilité et complexité : Rappel sur la notion de langage
Calculabilité et complexité/Rappel sur la notion de langage
 », n'a pu être restituée correctement ci-dessus.

On note un alphabet et un ensemble de mots, c'est-à-dire de suites finies composés avec les lettres de . On note également le mot vide, c'est-à-dire le mot composé d'aucune lettres.

Exemple :

et

Un langage est un sous-ensemble de . Par exemple avec on a .

Un automate tel que :

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

Un langage tel que 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 n’est pas algébrique, c’est ce qu'énonce le Lemme de la double étoile.

Puis on a les langages récursifs.