Langage récursifEn 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é.
Recursively enumerable languageIn mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages.
Langage contextuelEn informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context-sensitive language) est un langage formel engendré par une grammaire contextuelle. C'est un langage de type 1 dans la hiérarchie de Chomsky. Les langages contextuels sont les langages reconnus par les automates linéairement bornés, c'est-à-dire les machines de Turing dont la mémoire de travail est linéairement bornée en fonction de la taille de l'entrée.
Langage formelUn langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. La théorie des langages formels a pour objectif de décrire les langages formels. Les mots sont des suites d'éléments de cet alphabet ; les mots qui appartiennent à un langage formel particulier sont parfois appelés mots bien formés ou formules bien formées.
Langage algébriqueEn théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente, un langage algébrique est un langage reconnu par un automate à pile. Les langages algébriques forment les langages de dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML.
