Début de la boite de navigation du chapitre
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.
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.
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.