Langage récursif

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 L^c

et donc toutes les opérations booléennes.