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.
Objet libreEn mathématiques, la notion d'objet libre est l'un des concepts de base de l'algèbre générale. Elle appartient à l'algèbre universelle, car elle s'applique à tous les types de structures algébriques (avec des opérations finitaires). Elle se formule plus généralement dans le langage de la théorie des catégories : le foncteur « objet libre » est l'adjoint à gauche du foncteur d'oubli. Des exemples d'objets libres sont les groupes libres, les groupes abéliens libres, les algèbres tensorielles...
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.
Grammaire formelleUne grammaire formelle est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation logique, compilation (analyse syntaxique), en théorie de la calculabilité et dans le traitement des langues naturelles (tout particulièrement en ce qui concerne leur morphologie et leur syntaxe).
History monoidIn mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid provides a set of synchronization primitives (such as locks, mutexes or thread joins) for providing rendezvous points between a set of independently executing processes or threads.
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.
String operationsIn computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms. A string is a finite sequence of characters. The empty string is denoted by . The concatenation of two string and is denoted by , or shorter by . Concatenating with the empty string makes no difference: .
Algèbre de KleeneEn mathématiques, une algèbre de Kleene (du nom du logicien américain Stephen Cole Kleene) correspond à l'un des deux concepts suivants : Un treillis ordonné et distributif avec une involution satisfaisant les lois de De Morgan et l'inégalité x ∧ −x ≤ y ∨ −y. Ce qui fait que chaque algèbre booléenne est une algèbre de Kleene, la réciproque étant complément. À l'instar des algèbres de Boole qui sont basées sur les propositions logiques classiques, les algèbres de Kleene sont basées sur la logique ternaire de Kleene.
