Leçons de niveau 17

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

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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
Icon falscher Titel.svg
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 :

Calculabilité et complexité - automate.png

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.