Langages formels

Langages formels

Langage formel

Dans de nombreux contextes (scientifique, légal, etc.), 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 et informatique, un langage formel est formé :

La force des langages formels est de pouvoir faire abstraction 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 restera toujours un calcul de paye ou de matrice inverse, un théorème sur les groupes s'appliquera aussi bien sur l'ensemble des entiers que sur les transformations du cube de Rubik.

Sommaire

Le langage formel, outil de travail

Le langage formel d'une discipline scientifique 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.

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 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 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 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 du format externe au format interne de l'ordinateur. Les outils les plus connus sont Lex et Yacc. D'autres chercheurs ont défini la sémantique des langages de programmation.

Dans l'histoire des mathématiques et des sciences

Avant le XXe siècle

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 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 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 langage naturel ne s'étant montré ni assez précis ni assez concis.

Leibniz fut l'un des premiers à imaginer construire un langage formel, sous le nom de caractéristique universelle, qui pourrait permettre de réduire toutes les obscurités et équivocités du langage naturel. Un projet d'éclaircissement du langage naturel avait déjà été formulé par Hobbes et Locke, mais Leibniz l'a porté à un niveau d'universalité inédit. Bien qu'il échouât dans ce projet, celui-ci fut repris, et a été l'un des objectifs principaux du Cercle de Vienne, au début du XXe siècle.

Au XXe siècle

Au début du XXe siècle, le mathématicien David Hilbert, et avec lui, les formalistes pensaient pouvoir unifier les mathématiques grâce à une axiomatisation générale et à l'usage 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 qui démontre que dans tout système formel contenant l'arithmétique, 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, mais dont la négation non plus ne peut l'être. On aura beau formaliser les mathématiques, on trouvera toujours un énoncé formel dont la démonstration 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 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 contemporain est décrit dans cet article.

Les langages formels, objet 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 de la calculabilité. 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 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 de symboles a et b.

Le mot vide (le mot de longueur nulle) est autorisé et est noté ε. Bien que l'alphabet soit un ensemble fini 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 :

Construction d'un langage formel

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

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 vw où v 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_0, w_1, w_2, \dots w_n avec w_0, 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_n où n\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é

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 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é.

Voir aussi

Ce document provient de « Langage formel ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Langages formels de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Langages naturels — Langage naturel Un langage naturel, ou langage ordinaire , est une langue « normale » parlée par un être humain. En informatique, les langages naturels s opposent aux : langages machine : directement interprétables par le… …   Wikipédia en Français

  • Langages de programmation — 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, généralement un ordinateur. Le code source subit ensuite une transformation ou …   Wikipédia en Français

  • Famille abstraite de langages — En informatique théorique, et en particulier en théorie des langages formels, le terme famille abstraite de langages réfère à une notion qui généralise des caractéristiques communes aux langage rationnels, aux langages algébriques, aux langages… …   Wikipédia en Français

  • Classification des langages — Hiérarchie de Chomsky La hiérarchie de Chomsky est une classification naturelle (non arbitraire) des langages décrits par les grammaires formelles, découverte en 1956 par le linguiste Noam Chomsky. Tout langage pouvant être généré ou accepté par… …   Wikipédia en Français

  • Lemme d'itération pour les langages algébriques — Le Lemme d itération pour les langages algébriques, aussi connu sous le vocable Lemme de Bar Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels… …   Wikipédia en Français

  • Théorie des langages — En informatique, la théorie des langages a pour objectif de décrire les langages formels, vus comme moyen de communication, d un point de vue mathématique. Un langage formel[1] est un ensemble de mots. Un mot est une suite finie de symboles. L… …   Wikipédia en Français

  • Théorie des langages — ● Théorie des langages étude mathématique et construction abstraite de langages formels …   Encyclopédie Universelle

  • LOGIQUE MATHÉMATIQUE — La logique au sens étroit du terme, c’est à dire la logique formelle par opposition à l’épistémologie ou à la théorie de la connaissance, se propose de donner une théorie de l’inférence formellement valide. Elle considère comme valide toute… …   Encyclopédie Universelle

  • Langage formel — Dans de nombreux contextes (scientifique, légal, etc.), 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… …   Wikipédia en Français

  • Langage Formel — Dans de nombreux contextes (scientifique, légal, etc.), 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”