Théorie des langages

Abstract

Les langages r´ecursivement ´enum´erables sont le dernier type de langages qu’on a abord´e dans cette mati`ere. Ils sont g´en´er´es par des grammaires sans restriction et les mots d’un langage r´ecursivement ´enum´erables peuvent ˆetre reconnus par une machine de Turing. Les machines de Turing peuvent ˆetre utilis´ees pour la reconnaissance, la g´en´eration et le calcul. C’est cette derni`ere fonction qui nous a particuli`erement int´eress´e dans ce chapitre.