Langage récursif

Langage récursif

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.

Définitions

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.

Propriétés de fermeture

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 languages récursifs, alors les langages suivants sont aussi récursifs :

et donc toutes les opérations booléennes.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Langage récursif de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Langage Récursif — 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. Définitions Il y a plusieurs définitions équivalentes de langage récursif. On peut… …   Wikipédia en Français

  • Langage recursif — Langage récursif 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. Définitions Il y a plusieurs définitions équivalentes de langage… …   Wikipédia en Français

  • Recursif — Récursif Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Récursif — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Récursif », sur le Wiktionnaire (dictionnaire universel) Récursivité : une présentation générale… …   Wikipédia en Français

  • récursif — récursif, ive [ rekyrsif, iv ] adj. • v. 1968; angl. recursive; cf. récurrent ♦ Didact. Qui peut être répété un nombre indéfini de fois par l application de la même règle. Élément récursif dans une règle de réécriture (ling.). Processus récursif …   Encyclopédie Universelle

  • Langage Rationnel — Pour les articles homonymes, voir Langage, Régulier et Rationnel. Les expressions rationnelles permettent d engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les langages de type 3… …   Wikipédia en Français

  • Langage régulier — Langage rationnel Pour les articles homonymes, voir Langage, Régulier et Rationnel. Les expressions rationnelles permettent d engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les… …   Wikipédia en Français

  • Langage De Programmation Exotique — Un langage de programmation exotique est un langage de programmation imaginé comme un test des limites de la création de langages de programmation, un exercice intellectuel ou encore une blague, sans aucune intention de créer un langage… …   Wikipédia en Français

  • Langage de programmation ésotérique — Langage de programmation exotique Un langage de programmation exotique est un langage de programmation imaginé comme un test des limites de la création de langages de programmation, un exercice intellectuel ou encore une blague, sans aucune… …   Wikipédia en Français

  • Langage partiellement décidable — Récursivement énumérable En théorie de la calculabilité, un ensemble récursivement énumérable ou semi décidable est un ensemble qui est le domaine de définition, ou, de façon équivalente, l image d un fonction calculable (il faut ajouter l… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”