Langage formel
93943
31259220
2008-07-03T12:23:53Z
Vibraison
295924
/* Au XX{{e}} siècle */
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]] et [[informatique]], un langage formel est formé :
* d'un [[ensemble]] de mots obéissant à des règles logiques strictes (dites [[grammaire formelle]] ou syntaxe).
* d'une [[sémantique]] sous-jacente.
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 [[groupe (mathématiques)|groupe]]s s'appliquera aussi bien sur l'ensemble des [[Nombre entier|entiers]] que sur les transformations du [[cube de Rubik]].
==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, [[forme normale|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 [[ordinateur|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 XX{{e}} 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 é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 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 XX{{e}} siècle====
Au début du {{XXe siècle}}, le mathématicien [[David Hilbert]], et avec lui, les [[formalisme|formalistes]] pensaient pouvoir unifier les mathématiques grâce à une [[axiome|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 de Gödel|théorème d'incomplétude]] qui stipule 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 [[axiome]]s, 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 XX{{e}} 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 [[Langage formel mathématique|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îne de caractères|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 :
* l'ensemble des mots sur {''a'', ''b''},
* l'ensemble { <math>a^n</math> : ''n'' est un [[nombre premier]] },
* l'ensemble des programmes syntaxiquement corrects dans un [[langage de programmation]] donné,
* l'ensemble des mots d'entrée sur lesquels une [[machine de Turing]] donnée 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 (informatique)|automate]], comme une [[machine de Turing]] ou un [[machine à états finis|automate d'états finis]],
* l'ensemble des instances d'un [[problème de décision]] dont la réponse est OUI,
* des résultats d'[[inférence]]s.
Plusieurs opérations peuvent être utilisées pour fabriquer de nouveaux langages à partir de ceux qu'on connaît. Supposons que ''L''<sub>1</sub> et ''L''<sub>2</sub> soient des langages sur un certain alphabet commun.
* La ''[[concaténation]]'' de ''L''<sub>1</sub> et ''L''<sub>2</sub> est l'ensemble des mots de la forme ''vw'' où ''v'' est un mot de ''L''<sub>1</sub> et ''w'' est un mot de ''L''<sub>2</sub>. Notation : <math>L_1\cdot L_2</math> ou <math>L_1 L_2</math>.
* L'''[[opération ensembliste|intersection]]'' de ''L''<sub>1</sub> et ''L''<sub>2</sub> est l'ensemble des mots qui sont à la fois dans ''L''<sub>1</sub> et ''L''<sub>2</sub>. Notation : <math>L_1\cap L_2</math>.
* L'''[[opération ensembliste|union]]'' de ''L''<sub>1</sub> et ''L''<sub>2</sub> est l'ensemble des mots qui sont soit dans ''L''<sub>1</sub>, soit dans ''L''<sub>2</sub>. Notation : <math>L_1\cup L_2</math> ou <math>L_1 + L_2</math>.
* Le ''[[opération ensembliste|complémentaire]]'' d'un langage ''L''<sub>1</sub> est l'ensemble des mots sur son alphabet qui ne sont pas contenus dans ''L''<sub>1</sub>.
* Le ''quotient à droite'' de ''L''<sub>1</sub> et ''L''<sub>2</sub> est l'ensemble des mots ''v'' pour lesquels il existe un mot ''w'' de ''L''<sub>2</sub> tel que ''vw'' appartient à ''L''<sub>1</sub>. Notation : <math>L_1 / L_2</math>.
* La ''[[fermeture de Kleene]]'' de ''L''<sub>1</sub> est l'ensemble des mots qui peuvent s'écrire <math>w_1 w_2 \dots w_n </math> avec <math>w_1,w_2, \dots w_n \in L_1</math> et <math>n\ge 0</math>. Cet ensemble contient le mot vide ε parce que ''n'' = 0 est autorisé. Notation : <math>L_1^\star</math>.
* Le ''renversé'' de ''L''<sub>1</sub> contient les mots de ''L''<sub>1</sub> écrits à l'envers. Notation : <math>{L_1}^R</math>.
* Le ''mélangé'' de ''L''<sub>1</sub> et ''L''<sub>2</sub> est l'ensemble des mots pouvant s'écrire <math>v_1 w_1 v_2 w_2 \dots v_n w_n</math> où <math>n\ge 1</math>, <math>v_1 v_2 \dots v_n</math> est un mot de ''L''<sub>1</sub> et <math>w_1 w_2 \dots w_n</math> est un mot de ''L''<sub>2</sub>.
=== 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 [[calculabilité|théorie de la calculabilité]] et de la [[théorie de la complexité]].
==Voir aussi==
*[[Langage formel mathématique]]
*[[Langage de programmation]]
*[[Grammaire formelle]]
*[[Théorie des langages]]
[[Catégorie:Langage formel|*]]
[[ar:لغة شكلية]]
[[bg:Формален език]]
[[bs:Formalni jezik]]
[[cs:Formální jazyk]]
[[da:Formelt sprog]]
[[de:Formale Sprache]]
[[el:Τυπική γλώσσα]]
[[en:Formal language]]
[[es:Lenguaje formal]]
[[fa:زبانهای فرمال]]
[[fi:Formaali kieli]]
[[he:שפה פורמלית]]
[[hi:औपचारिक भाषा]]
[[hr:Formalni jezik]]
[[hu:Formális nyelv]]
[[it:Linguaggio formale (matematica)]]
[[ja:形式言語]]
[[ko:형식 언어]]
[[mk:Формален јазик]]
[[nl:Formele taal]]
[[pl:Język formalny]]
[[pt:Linguagem formal]]
[[ro:Limbaje formale]]
[[ru:Формальный язык]]
[[simple:Formal language]]
[[sk:Formálny jazyk]]
[[tr:Biçimsel dil kuramı]]
[[uk:Формальна мова]]
[[zh:形式语言]]