En mathématiques, en logique et en informatique, un langage récursif est un type de langage formel qui est aussi appelé récursif, décidable, ou Turing-decidable. Il y a plusieurs définitions équivalentes de langage récursif. On peut définir cette notion directement, comme une généralisation de celle d'ensemble récursif (des sous-ensembles d'entiers ou de uples d'entiers), ou passer par des codages dans les entiers, en utilisant la théorie de la calculabilité. Pour une définition directe on peut employer des machines de Turing qui utilisent l'alphabet du langage. Un langage récursif est alors un langage formel reconnu par une machine de Turing : la machine s'arrête toujours, elle accepte une entrée si et seulement si celle-ci est un mot du langage. De façon équivalente, un langage est récursif si et seulement si lui et son complémentaire (dans l'ensemble de tous les mots sur l'alphabet du langage) sont récursivement énumérables. Les langages récursivement énumérables sont les langages engendrés par les grammaires générales. Tous les langages récursifs sont aussi récursivement énumérables, mais la réciproque est fausse. Les autres langages de la hiérarchie de Chomsky, comme les langages réguliers sont récursifs. Pour des raisons intrinsèque à la notion de calculabilité (liées à l'indécidabilité du problème de l'arrêt), on ne peut donner de forme générale « simple » (récursive) des grammaires qui engendrent tous les langages récursifs et seulement ceux-ci. La classe des langages récursifs n'apparait donc pas en tant que telle dans la hiérarchie de Chomsky. La classe des langages récursifs est close pour un certain nombre d'opérations qui sont détaillées ensuite. On montre que si L et P sont deux langages récursifs, alors les langages suivants sont aussi récursifs : La fermeture de Kleene L* de L La concaténation L . P de L et P (le langages des mots obtenus par concaténation d'un mot de L et d'un mot de P) Les opérations ensemblistes booléennes L'union L∪P L'intersection L∩P Le complémentaire Lc et donc toutes les opérations booléennes.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.