Système formelUn système formel est une modélisation mathématique d'un langage en général spécialisé. Les éléments linguistiques, mots, phrases, discours, etc., sont représentés par des objets finis (entiers, suites, arbres ou graphes finis...). Le propre d'un système formel est que la correction au sens grammatical de ses éléments est vérifiable algorithmiquement, c'est-à-dire que ceux-ci forment un ensemble récursif.
Automate finithumb|upright=2|Fig. 1 : Une hiérarchie d'automates. Un automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine ou FSM) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie.
Problème de la décisionEn logique mathématique, on appelle problème de la décision ou, sous son nom d'origine en allemand, Entscheidungsproblem, le fait de déterminer de façon mécanique (par un algorithme) si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s'il se dérive dans un système de déduction sans autres axiomes que ceux de l'égalité (exemples : système à la Hilbert, calcul des séquents, déduction naturelle).
Chaîne de caractèresEn informatique, une chaîne de caractères est à la fois conceptuellement une suite ordonnée de caractères et physiquement une suite ordonnée d' unités de code (code unit). La chaîne de caractères est un type de donnée dans de nombreux langages informatiques. La traduction en anglais est string. À l'époque des pionniers, on a communément confondu chaîne de caractères et chaîne d'octets, ce qui prête aujourd'hui à confusion, lorsque l'on ne veut pas se limiter à 255 caractères.
Langage rationnelEn théorie des langages, les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes : ce sont les langages décrits par les expressions régulières ou rationnelles, d'où le nom de langages réguliers ; ce sont les langages obtenus, à partir des lettres et de l'ensemble vide, par les opérations rationnelles, à savoir l'union, le produit et l'étoile de Kleene, d'où le nom de langages rationnels ; ce sont les langages reconnus par des auto
Mathématiquesthumb|upright|Raisonnement mathématique sur un tableau. Les mathématiques (ou la mathématique) sont un ensemble de connaissances abstraites résultant de raisonnements logiques appliqués à des objets divers tels que les ensembles mathématiques, les nombres, les formes, les structures, les transformations ; ainsi qu'aux relations et opérations mathématiques qui existent entre ces objets. Elles sont aussi le domaine de recherche développant ces connaissances, ainsi que la discipline qui les enseigne.
Grammaire non contextuelleEn linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme où est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par , sans tenir compte du contexte où il apparaît.
Formule logiqueEn logique on dit d’une suite finie de lettres qu’elle est une formule, ou parfois formule bien formée, d'un langage logique donné lorsqu’elle peut être construite en appliquant une combinaison des règles de la grammaire formelle associée, on parle de la syntaxe du langage. Informellement les formules sont les assemblages de lettres auxquels il est possible de donner une signification en termes de valeur de vérité (Vrai, ou Faux). Les formules logiques sont l'équivalent des phrases du langage naturel.
Forme normale de ChomskyEn informatique théorique, et notamment en théorie des langages, une grammaire non contextuelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : ou ; ou où sont des symboles non terminaux, est un symbole terminal, est l'axiome de la grammaire, et est le mot vide. Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.
Alphabet (formal languages)In formal language theory, an alphabet, sometimes called a vocabulary, is a non-empty set of indivisible symbols/glyphs, typically thought of as representing letters, characters, digits, phonemes, or even words. Alphabets in this technical sense of a set are used in a diverse range of fields including logic, mathematics, computer science, and linguistics. An alphabet may have any cardinality ("size") and depending on its purpose maybe be finite (e.g., the alphabet of letters "a" through "z"), countable (e.
