Langage formel
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Dans de nombreux contextes (scientifique, légal, etc.) l'on désigne par langage formel un mode d'expression plus formalisé et plus précis (les deux n'allant pas nécessairement de pair) que le langage de tous les jours (voir langage naturel).

En mathématiques, logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la fois raison, langage, et raisonnement) est dans une première...) et informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines telles que les ordinateurs,...), un langage formel (Dans de nombreux contextes (scientifique, légal, etc.) l'on désigne par langage formel un mode d'expression plus formalisé et plus précis (les deux n'allant pas nécessairement de pair) que le langage de tous les jours...) est formé :

  • d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) de mots obéissant à des règles logiques strictes (dites grammaire formelle ou syntaxe).
  • d'une sémantique sous-jacente.

La force (Le mot force peut désigner un pouvoir mécanique sur les choses, et aussi, métaphoriquement, un pouvoir de la volonté ou encore une vertu morale...) des langages formels est de pouvoir faire abstraction ( En philosophie, l'abstraction désigne à la fois une opération qui consiste a isoler par la pensée une ou plusieurs qualités d'un objet concret pour en former une représentation intellectuelle, et le produit de cette opération. ...) de la sémantique, ce qui rend les théories réutilisables dans plusieurs modèles. Ainsi, alors qu'un calcul particulier de paye ou de matrice inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un élément y tel que...) restera toujours un calcul de paye ou de matrice inverse, un théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à partir...) sur les groupes s'appliquera aussi bien sur l'ensemble des entiers que sur les transformations du cube (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus...) de Rubik.

Le langage formel, outil (Un outil est un objet finalisé utilisé par un être vivant dans le but d'augmenter son efficacité naturelle dans l'action. Cette augmentation se traduit par la simplification des actions entreprises, par une plus grande rentabilisation de...) de travail

Le langage formel d'une discipline scientifique (Un scientifique est une personne qui se consacre à l'étude d'une science ou des sciences et qui se consacre à l'étude d'un domaine avec la rigueur et les méthodes scientifiques.) est un langage obéissant à une syntaxe formelle stricte, servant à exposer des énoncés de manière précise, si possible concise et sans ambiguïté ; ce qui l'oppose au langage naturel (Un langage naturel est une langue « normale » parlée par un être humain.).

Langage formel contre langage naturel

Le langage formel a pour avantage de rendre aisées la manipulation et la transformation d'énoncés. Des règles de transformation précises (développement de formules logiques, formes normales, contrapositions, commutativité, associativité, etc.) peuvent être appliquées sans même connaître la signification de l'énoncé transformé ou la signification de la transformation. C'est un outil d'exploration (L'exploration est le fait de chercher avec l'intention de découvrir quelque chose d'inconnu.) puissant, et c'est le seul langage qui permette aux machines de " faire des mathématiques ".

L'inconvénient est évident : ne pas connaître le sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par...) de l'énoncé empêche de savoir quelles sont les transformations pertinentes et nuit à l'intuition du raisonnement. Ainsi, il est bon de savoir lire rapidement un énoncé en langage formel et de le traduire tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) aussi rapidement en un ou plusieurs énoncés du langage naturel, plus significatif.

Compréhension à l'aide d'ordinateurs

Dès le début de l'informatique les chercheurs ont développé des outils d'aide à la traduction des langages, afin de passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) du format externe au format interne (En France, ce nom désigne un médecin, un pharmacien ou un chirurgien-dentiste, à la fois en activité et en formation à l'hôpital ou en cabinet pendant une durée...) de l'ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des...). Les outils les plus connus sont Lex et Yacc (Lex et yacc sont des outils très populaires de génération d'analyseurs lexicaux (Lex) et syntaxiques (Yacc) en langage C. « Yacc » est l'acronyme de Yet Another...). D'autres chercheurs ont défini la sémantique des langages de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception...).

Dans l'histoire des mathématiques (L’histoire des mathématiques s'étend sur plusieurs millénaires et dans de nombreuses régions du globe allant de la Chine à l'Amérique centrale. Dans la mesure où historiquement la recherche en mathématiques s'est concentrée...) et des sciences

Avant le XXe siècle (Un siècle est maintenant une période de cent années. Le mot vient du latin saeculum, i, qui signifiait race, génération. Il a ensuite indiqué la durée d'une...)

Les mathématiques existent depuis l'antiquité mais la manière de les exprimer a énormément évolué.

Comme pour toute discipline, le langage de la discipline ne préexiste évidemment pas à la discipline elle-même. Il a donc fallu utiliser des langues qui n'ont pas été construites pour les mathématiques, qui peu à peu se sont enrichies d'un jargon spécifique.

Ainsi, bien des énoncés mathématiques anciens nous paraissent aujourd'hui avoir une formulation (La formulation est une activité industrielle consistant à fabriquer des produits homogènes, stables et possédant des propriétés spécifiques,...) plutôt alambiquée, surchargée de périphrases quand il n'existe pas de mots pour désigner certains concepts.

Le jargon s'est donc enrichi au cours des siècles et continue encore d'évoluer.

Parallèlement à ce phénomène, s'est progressivement formé le langage formel qui est devenu celui que nous connaissons, le jargon naturel ne s'étant montré ni assez précis ni assez concis.

Au XXe siècle

Au début du XXe siècle, le mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son activité principale. Ce terme recouvre...) David Hilbert, et avec lui, les formalistes pensaient pouvoir unifier les mathématiques grâce à une axiomatisation générale et à l'usage (L’usage est l'action de se servir de quelque chose.) d'un langage formel commun.

Cette vision des mathématiques fut mise à mal en 1931 lorsque le logicien Kurt Gödel annonça son célèbre théorème d'incomplétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut...) qui stipule (En botanique, les stipules sont des pièces foliaires, au nombre de deux, en forme de feuilles réduites située de part et d'autre du pétiole, à sa base, au point...) que dans tout système formel (Un système formel est un ensemble de formules, ou expressions formelles, que l’on peut interpréter comme des noms, des phrases, ou de toute autre façon. Ils sont des...) contenant l'arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l'appelle plus généralement la « science des...), il existe au moins une proposition indécidable.

Pour revenir aux langages formels, la conséquence de ce théorème est la suivante : étant donné un langage formel, ses axiomes, et son système de déduction formel capables d'exprimer l'arithmétique, on peut énoncer une proposition de ce langage qui ne peut pas être prouvée dans ce système, ainsi que sa négation. On aura beau formaliser les mathématiques, on trouvera toujours un énoncé formel dont la démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de...) oblige à quitter ou élargir ce formalisme en ajoutant de nouveaux axiomes, ce qui introduira immanquablement de nouveaux énoncés indécidables. Ainsi l'approche formaliste, qui reste pourtant valable, a désormais des limites connues.

Dans la seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une mesure d'angle plan. La...) moitié du XXe siècle, l'avènement des ordinateurs et de l'informatique a donné une place particulière aux langages formels en tant qu'outils et en tant qu'objets d'étude, ce qui était relativement nouveau.

Aujourd'hui (début du XXIe siècle)

Les traités de mathématiques utilisent à la fois langage formel et langage naturel. Le langage formel est réservé aux passages techniques et aux énoncés suffisamment simples pour ne pas nécessiter d'amples explications, et les résultats importants sont souvent explicités à la fois en langage formel et naturel.

Le langage formel mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les...) contemporain est décrit dans cet article.

Les langages formels, objet (De manière générale, le mot objet (du latin objectum, 1361) désigne une entité définie dans un espace à trois dimensions, qui a une fonction précise, et...) d'étude

Les langages formels sont aussi l'objet d'étude d'une branche à part entière de la logique et de l'informatique théorique. Cette étude est fortement liée à la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une...) de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la notion intuitive de fonction calculable est aussi...). En effet le propre d'un langage formel, en tant que langage, c'est de pouvoir être traité par un ordinateur, ou par son modèle formel : la machine de Turing.

Définitions

En tant qu'objet d'étude, un langage formel est défini comme un ensemble de mots de longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est celle de l’objet complètement...) finie (c'est-à-dire chaînes de caractères) déduit d'un certain alphabet fini, c'est-à-dire une partie du monoïde libre sur cet alphabet.

Typiquement, un alphabet serait : {a, b}, et un mot sur cet alphabet serait : ababba.

Un langage typique sur cet alphabet, et qui contiendrait ce mot, serait l'ensemble de tous les mots qui contiennent le même nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de symboles a et b.

Le mot vide (Le vide est ordinairement défini comme l'absence de matière dans une zone spatiale.) (le mot de longueur nulle) est autorisé et est noté ε. Bien que l'alphabet soit un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) et que chaque mot ait une longueur finie, un langage peut très bien contenir une infinité de mots (parce que la longueur de ses mots peut ne pas être bornée).

Exemples

Quelques exemples de langages formels :

  • l'ensemble des mots sur {a, b},
  • l'ensemble { an : n est un nombre premier (Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même). Cette définition exclut 1, qui n'a qu'un seul diviseur entier...) },
  • l'ensemble des programmes syntaxiquement corrects dans un langage de programmation (Un langage de programmation est un langage informatique, permettant à un être humain d'écrire un code source qui sera analysé par une machine,...) donné,
  • l'ensemble des mots d'entrée sur lesquels une machine de Turing donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) s'arrête.

Construction d'un langage formel

Un langage formel peut être spécifié par différents moyens, comme :

  • les mots produits par des règles de production dites aussi règles d'une grammaire formelle (voir classification des langages),
  • les mots générés par une expression rationnelle,
  • les mots acceptés par un certain automate (Un automate est un dispositif se comportant de manière automatique, c'est-à-dire sans intervention d'un humain. Ce comportement peut être figé, le...), comme une machine de Turing ou un automate d'états finis,
  • l'ensemble des instances d'un problème de décision (En logique mathématique, on appelle problème de la décision 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,...) dont la réponse est OUI,
  • des résultats d'inférences.

Plusieurs opérations peuvent être utilisées pour fabriquer de nouveaux langages à partir de ceux qu'on connaît. Supposons que L1 et L2 soient des langages sur un certain alphabet commun.

  • La concaténation de L1 et L2 est l'ensemble des mots de la forme vwv est un mot de L1 et w est un mot de L2. Notation : L_1\cdot L_2 ou L1L2.
  • L'intersection de L1 et L2 est l'ensemble des mots qui sont à la fois dans L1 et L2. Notation : L_1\cap L_2.
  • L'union de L1 et L2 est l'ensemble des mots qui sont soit dans L1, soit dans L2. Notation : L_1\cup L_2 ou L1 + L2.
  • Le complémentaire d'un langage L1 est l'ensemble des mots sur son alphabet qui ne sont pas contenus dans L1.
  • Le quotient à droite de L1 et L2 est l'ensemble des mots v pour lesquels il existe un mot w de L2 tel que vw appartient à L1. Notation : L1 / L2.
  • La fermeture de Kleene de L1 est l'ensemble des mots qui peuvent s'écrire w_1 w_2 \dots w_n avec w_1,w_2, \dots w_n \in L_1 et n\ge 0. Cet ensemble contient le mot vide ε parce que n = 0 est autorisé. Notation : L_1^\star.
  • Le renversé de L1 contient les mots de L1 écrits à l'envers. Notation : {L_1}^R.
  • Le mélangé de L1 et L2 est l'ensemble des mots pouvant s'écrire v_1 w_1 v_2 w_2 \dots v_n w_nn\ge 1, v_1 v_2 \dots v_n est un mot de L1 et w_1 w_2 \dots w_n est un mot de L2.

Appartenance, calculabilité et complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique,...)

Des questions typiques que l'on se pose à propos d'un langage formel sont les suivantes:

  • Peut-on décider par algorithme si un mot donné appartient à ce langage?
  • Si oui, quelle est la complexité algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de...) d'une telle réponse?

Ces questions relèvent des domaines de la théorie de la calculabilité et de la théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la...).

Page générée en 1.388 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique