Langage récursif - Recursive language

En mathématiques , en logique et en informatique , un langage formel (un ensemble de séquences finies de symboles tirés d'un alphabet fixe ) est dit récursif s'il s'agit d'un sous - ensemble récursif de l'ensemble de toutes les séquences finies possibles sur l'alphabet du langage. De manière équivalente, un langage formel est récursif s'il existe une machine de Turing totale (une machine de Turing qui s'arrête pour chaque entrée donnée) qui, lorsqu'on lui donne une séquence finie de symboles en entrée, l'accepte s'il appartient au langage et le rejette autrement. Les langages récursifs sont aussi appelés décidables .

Le concept de décidabilité peut être étendu à d'autres modèles de calcul . Par exemple on peut parler de langages décidables sur une machine de Turing non déterministe . Par conséquent, chaque fois qu'une ambiguïté est possible, le synonyme utilisé pour "langage récursif" est langage Turing-décidable , plutôt que simplement décidable .

La classe de tous les langages récursifs est souvent appelée R , bien que ce nom soit également utilisé pour la classe RP .

Ce type de langage n'était pas défini dans la hiérarchie de Chomsky ( Chomsky 1959 ). Tous les langages récursifs sont également récursivement énumérables . Tous les réguliers , contexte sans et contextuelles langues sont récursives.

Définitions

Il existe deux définitions majeures équivalentes pour le concept de langage récursif :

1. Un langage formel récursif est un sous-ensemble récursif dans l' ensemble de tous les mots possibles sur l' alphabet de la langue .
2. Un langage récursif est un langage formel pour lequel il existe une machine de Turing qui, lorsqu'elle est présentée avec une chaîne d' entrée finie , s'arrête et accepte si la chaîne est dans le langage, et s'arrête et rejette dans le cas contraire. La machine de Turing s'arrête toujours : on l'appelle décideur et on dit qu'elle décide du langage récursif.

Par la deuxième définition, tout problème de décision peut être montré comme décidable en présentant un algorithme qui se termine sur toutes les entrées. Un problème indécidable est un problème qui n'est pas décidable.

Exemples

Comme indiqué ci-dessus, chaque langage contextuel est récursif. Ainsi, un exemple simple de langage récursif est l'ensemble L={abc, aabbcc, aaabbbccc, ...} ; plus formellement, l'ensemble

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ pour certains }}n\geq 1\,\}}$

est contextuel et donc récursif.

Les exemples de langages décidables qui ne sont pas contextuels sont plus difficiles à décrire. Pour un tel exemple, une certaine familiarité avec la logique mathématique est requise : l'arithmétique de Presburger est la théorie du premier ordre des nombres naturels avec addition (mais sans multiplication). Alors que l'ensemble des formules bien formées de l'arithmétique de Presburger est sans contexte, chaque machine de Turing déterministe acceptant l'ensemble des déclarations vraies de l'arithmétique de Presburger a un temps d'exécution dans le pire des cas d'au moins , pour une constante c > 0 ( Fischer & Rabin 1974 ). Ici, n désigne la longueur de la formule donnée. Étant donné que chaque langage contextuel peut être accepté par un automate linéaire borné et qu'un tel automate peut être simulé par une machine de Turing déterministe avec un temps d'exécution dans le pire des cas au plus pour une constante c , l'ensemble des formules valides dans l'arithmétique de Presburger n'est pas sensible au contexte. Du côté positif, on sait qu'il existe une machine de Turing déterministe fonctionnant en temps au plus triplement exponentiel en n qui décide de l'ensemble des vraies formules en arithmétique de Presburger ( Oppen 1978 ). Il s'agit donc d'un exemple de langage décidable mais non contextuel. ${\displaystyle 2^{2^{cn}}}$${\style d'affichage c^{n}}$

Propriétés de fermeture

Les langages récursifs sont fermés sous les opérations suivantes. Autrement dit, si L et P sont deux langages récursifs, les langages suivants sont également récursifs :

• La star de Kleene ${\displaystyle L^{*}}$
• L'image φ(L) sous un homomorphisme e-libre φ
• La concaténation ${\displaystyle L\circ P}$
• L'Union ${\displaystyle L\cup P}$
• Le carrefour ${\displaystyle L\cap P}$
• Le complément de ${\style d'affichage L}$
• La différence d'ensemble ${\displaystyle LP}$

La dernière propriété découle du fait que la différence d'ensemble peut être exprimée en termes d'intersection et de complément.

Voir également

• Langage récursivement énumérable
• Récursivité

Les références

• Michael Sipser (1997). "Décidabilité" . Introduction à la théorie du calcul . Éditions PWS. p.  151-170 . ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). "Sur certaines propriétés formelles des grammaires" . Informations et contrôle . 2 (2) : 137-167. doi : 10.1016/S0019-9958 (59) 90362-6 .
• Fischer, Michael J. ; Rabin, Michael O. (1974). « Complexité super-exponentielle de l'arithmétique de Presburger » . Actes du Symposium SIAM-AMS en Mathématiques Appliquées . 7 : 27-41.
• Oppen, Derek C. (1978). "Une ^borne supérieure 2 ^{2 2 pn} sur la complexité de l'arithmétique de Presburger" . J. Informatique. Syst. Sci . 16 (3) : 323-332. doi : 10.1016/0022-0000(78)90021-1 .