Voir la source de Langage formel

{{autre4|les langages formels en informatique|d'autres usages|Formalisation (mathématiques)}}
[[File:Syntax tree.svg|thumb|upright=1.4|Structure de la phrase ''[[Colorless green ideas sleep furiously]]'' qui est syntaxiquement bien formée, mais n'a pas de sens (exemple historique de [[Noam Chomsky]], 1957).]]
Un '''langage formel''', en [[mathématiques]], en [[informatique]] et en [[linguistique]], est un ensemble de [[mot (mathématiques)|mots]]<ref>Un {{cita|mot}} au sens mathématique du terme est une suite de symboles pris dans un ensemble dit {{cita|alphabet}}.</ref>. L'[[alphabet]] d'un langage formel est l'ensemble des symboles, lettres ou [[Lexème (linguistique)|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 [[formule bien formée|formules bien formées]]. Un langage formel est souvent défini par une [[grammaire formelle]], telle que les [[grammaire algébrique|grammaires algébriques]] et analysé par des [[théorie des automates|automates]].

== Objectifs ==
La théorie des langages formels étudie les aspects purement [[syntaxe|syntaxiques]] de tels langages, c'est-à-dire leur structure interne formelle. La théorie des langues est issue de la [[linguistique]], comme moyen de comprendre les régularités syntaxiques de [[Langue naturelle|langues naturelles]] :
* En informatique, les langages formels sont souvent utilisés comme base pour la définition des [[Langage de programmation|langages de programmation]] et d'autres systèmes ; les mots d'un langage comportent alors aussi un sens, une [[sémantique]].
* En [[théorie de la complexité des algorithmes]], les [[problème de décision|problèmes de décision]] sont généralement définis comme des langages formels, et les [[classe de complexité|classes de complexité]] sont définies comme les ensembles de langages formels qui peuvent être analysés par des machines ayant des ressources de calcul limitées.
* En [[logique mathématique]], les langages formels sont utilisés pour représenter la syntaxe des [[système axiomatique|systèmes axiomatiques]], et l'[[Logicisme|attitude formaliste en mathématique ou logicisme]] affirme qu'en principe, les mathématiques peuvent se ramener à la manipulation syntaxique de langages formels.

L'étude des langages formels comporte l'ensemble des moyens de description et d'analyse de ces langages, comme les [[grammaire formelle|grammaires formelles]] pour la génération et les [[théorie des automates|automates]] pour la reconnaissance, mais elle s'intéresse aussi à l'[[apprentissage automatique]] et la [[traduction automatique]] des langages. Dans le domaine de la traduction, la théorie des langages s'applique aux [[compilateur]]s de langages de programmation.

== Mots et langages ==
{{Article détaillé|Mot (mathématiques)}}

=== Définitions ===
On se donne un ensemble <math>A</math>, appelé '''alphabet''' dont les éléments sont appelés des '''lettres'''.
* Un '''mot''' de longueur ''k'' est une suite <math>u=(a_1,a_2,...,a_k)</math> de ''k'' lettres. En pratique, on utilise la notation condensée <math>u= a_1a_2\cdots a_k</math>.
* L'ensemble des mots sur l'alphabet <math>A</math> est noté <math>A^*</math>.
* Le [[Chaîne vide|mot vide]], de longueur <math>0</math>, est noté <math>1</math>, ou parfois <math>\varepsilon</math> (ou encore <math>\Lambda</math> pour le distinguer des <math>\varepsilon</math>-transitions dans les automates finis).
* On définit sur <math>A^*</math>, une [[loi de composition interne]] appelée [[concaténation]]. Elle associe à deux mots <math>a_1 \cdots a_n</math> et <math>b_1 \cdots b_m</math> le mot <math>a_1 \cdots a_nb_1 \cdots b_m</math> (de longueur <math>n+m</math>).

Cette loi de composition interne est associative et admet le mot vide pour élément neutre (ce qui justifie la notation <math>1</math>). Par conséquent l'ensemble <math>A^*</math>, muni de cette loi, est un [[monoïde]]. C'est un [[Monoïde#Monoïde libre|monoïde libre]] au sens de l'algèbre.

Un '''langage formel''' est un ensemble de mots sur un alphabet fini, c'est-à-dire une partie du [[monoïde]] libre sur cet alphabet.

=== Exemples ===
Quelques exemples de langages formels :
* l'ensemble de tous les mots sur <math>\{a, b\}</math>,
* l'ensemble des mots de la forme <math>a^n</math>, où <math>n</math> 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,
* l'ensemble des 1000 mots les plus fréquents dans une langue donnée.

=== Construction d'un langage formel ===
Un langage formel peut être spécifié par différents moyens. Ce qui est recherché, c'est une méthode ou un mécanisme fini, et explicite, qui permet de produire ou d'analyser un langage en général infini. Parmi ces méthodes, il y a :
* les [[grammaire formelle|grammaires formelles]]. Les mots sont produits par des règles, en nombre fini, qui s'appliquent dans des conditions précises. On obtient une classification de langages appelée [[hiérarchie de Chomsky]] ;
* les [[expression rationnelle|expressions rationnelles]]. Les mots sont décrits selon un symbolisme qui permet de décrire des successions, des répétitions, des alternatives. C'est un moyen très répandu pour la recherche de mots dans des textes ;
* les [[théorie des automates|automates]]. Ce sont des machines mathématiques qui reconnaissent une certaine catégorie de mots. Parmi eux, il y a les [[Système de transition d'états|systèmes de transitions d'états]], les [[machine de Turing|machines de Turing]] ou les [[automate fini|automates finis]] ;
* l'ensemble des instances d'un [[problème de décision]] dont la réponse est OUI ;
* divers systèmes [[Logique de description|logiques de description]] à l'aide de formules logiques.
* des [[réécriture (informatique) | systèmes de réécriture]]. Une famille particulière est formée des [[langage congruentiel|langages congruentiels]].

=== 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 ont des liens avec la [[calculabilité]] et de la [[Théorie de la complexité (informatique théorique)|théorie de la complexité]].

== Familles de langages ==
Les langages sont regroupés en familles de langages. La Hiérarchie de Chomsky nous donne quatre types de grammaire, chaque type de grammaire générant une famille de langage.
* Les grammaires de type 0 génèrent la famille des [[Récursivement énumérable|langages récursivement énumérables]]. Ce sont exactement les langages reconnaissables par une [[machine de Turing]].
* Les grammaires de type 1 génèrent la famille des [[Langage contextuel|langages contextuels]]. Ce sont exactement les langages reconnaissables par les [[Automate linéairement borné|automates linéairement bornés]].
* Les grammaires de type 2 génèrent la famille des [[Langage algébrique|langages algébriques]]. Ce sont les langages reconnaissables par les [[Automate à pile|automates à pile]].
* Les grammaires de type 3 génèrent la famille des [[Langage rationnel|langages rationnels]]. Ce sont les langages reconnaissables par les [[Automate fini|automates finis]].

Ces ensembles de langages sont tous inclus les uns dans les autres et sont ici donnés de l'ensemble le plus grand au plus petit. Donc, tout [[langage rationnel]] est [[Langage algébrique|algébrique]], qui est lui-même [[Langage contextuel|contextuel]], qui est lui-même [[récursivement énumérable]].

Entre ces 4 familles de langages, on peut noter des familles qui ne font pas partie de la hiérarchie de Chomsky, mais qui restent remarquables par leurs définitions et leurs propriétés.

Les [[Langage algébrique#Langages déterministes|langages algébriques déterministes]] sont les langages reconnaissables par les [[Automate à pile#Automate à pile déterministe|automates à pile déterministes]], et sont donc strictement inclus dans la famille des langages algébriques.

Les [[Langage récursif|langages récursifs]] sont les langages reconnus par une machine de Turing, et dont le complémentaire est aussi reconnu par une machine de Turing. Ils sont donc strictement inclus dans les [[Récursivement énumérable|langages récursivement énumérables]].

== Opérations sur les langages formels ==
Plusieurs opérations peuvent être utilisées pour fabriquer de nouveaux langages à partir de langages donnés. Supposons que ''L'' et ''M'' soient des langages sur un certain alphabet commun.

=== Opérations ensemblistes ===
Les opérations ensemblistes ''[[opération ensembliste|intersection]]'', ''[[opération ensembliste|union]]'' et ''[[opération ensembliste|complémentation]]'' sont définies comme pour tout ensemble.

=== Concaténation ou produit ===
La ''[[concaténation]]'' de <math>L</math> et de <math>M</math>, notée simplement <math>LM</math> est l'ensemble des mots de la forme <math>xy</math> où <math>x</math> est un mot de <math>L</math> et <math>y</math> est un mot de <math>M</math>.

=== Quotients ou résiduels ===
Le ''quotient à gauche'' <math>x^{-1}L</math> de <math>L</math> par un mot <math>x</math> est l'ensemble des mots <math>y</math> tels que <math>xy</math> appartient à <math>L</math>. Le quotient à gauche est aussi appelé ''résiduel''.

Le ''quotient à droite'' <math>Lx^{-1}</math> de <math>L</math> par un mot <math>x</math> est défini symétriquement comme l'ensemble des mots <math>y</math> tels que <math>yx</math> appartient à <math>L</math>.

Le ''quotient à gauche'' et le ''quotient à droite'' s'étendent aux langages. Ainsi, le quotient à gauche de <math>L</math> par un langage <math>M</math>, noté <math>M^{-1}L</math>, est la réunion des langages <math>x^{-1}L</math> pour <math>x</math> dans <math>M</math>.

=== Étoile de Kleene ===
L'''[[étoile de Kleene]]'' de ''L'' est l'ensemble noté <math>L^\star</math> composé des mots de la forme <math>u_1.u_2. \dots. u_n </math> avec <math>n\geqslant 0</math> et <math>u_1, u_2, \dots, u_n \in L</math>. Cet ensemble contient le [[Chaîne vide|mot vide]].

=== Retourné ou image miroir ===
Le ''renversé'' de ''L'', noté <math>L^R</math> ou <math>\tilde L</math> contient les [[mot (mathématiques)|mots miroirs]] des mots de ''L'', c'est-à-dire les mots de ''L'' lus de droite à gauche.

=== Mélange ou « shuffle » ===
Le ''mélange'' de ''L'' et ''M'', noté ''L'' Ш ''M'', est l'ensemble des mots pouvant s'écrire <math>u_1 v_1u_2 v_2 \dots u_n v_n</math> où <math>n\geqslant 0</math> et <math>u_1, \dots, u_n, v_1, \dots, v_n</math> sont des mots (éventuellement vides) tels que <math>u_1 u_2 \dots u_n</math> soit un mot de ''L'' et <math>v_1 v_2 \dots v_n</math> soit un mot de ''M''. Par exemple<ref>Pour bien comprendre cet exemple, on écrit les lettres du deuxième mot en majuscules. Alors on obtient :
:<math>\{ab\}</math> Ш <math>\{BA\} = \{abBA, aBbA, BAab, BaAb, BabA, aBAb\}</math>
et quand on remplace les majuscules par les minuscules, on a bien les mots indiqués.</ref> <math>\{ab\}</math> Ш <math>\{ba\} = \{abba, baab, baba, abab\}</math>.

=== Morphisme et morphisme inverse ===
Une application <math>f : A^*\to B^*</math> est un ''morphisme'' ou ''homomorphisme'' si <math>f(xy)=f(x)f(y)</math> pour tous mots <math>x, y</math> de <math>A^*</math>. L'image homomorphe d'un langage <math>L</math> sur <math>A</math> est l'ensemble
:<math>f(L)=\{f(x)\mid x\in L\}</math>.

Par abus de langage, on appelle ''morphisme inverse'' l'inverse d'un morphisme. Le morphisme inverse de <math>f : A^*\to B^*</math> est la fonction notée <math>f^{-1}</math> de <math>B^*</math> dans l'ensemble des parties de <math>A^*</math> définie par
:<math>f^{-1}(y) =\{x\in A^* \mid f(x)=y\}</math>.

Ce n'est en général pas un morphisme. L'image par un morphisme inverse d'un langage <math>M</math> sur <math>B</math> est le langage
:<math>f^{-1}(M) =\bigcup_{y\in M} f^{-1}(y) </math>.

Un morphisme est ''non effaçant'' ou ''croissant'' ou, par imitation de l'anglais, ''ε-free'' si l'image d'une lettre n'est jamais le mot vide. Dans ce cas, la longueur de l'image d'un mot est supérieure ou égale à celle du mot.

=== Propriétés de clôture ===
Une question commune sur ces opérations est de connaitre les propriétés de clôture de chaque famille de langage pour chacune de ces opérations, c'est-à-dire si le langage issu d'une opération reste dans la même famille de langages que les langages dont il est issu.

{| class="wikitable"
|+'''Tableau des propriétés de clôture<ref>Preuves dans {{Langages formels, calculabilité et complexité}} <!-- id: Carton2008 --></ref> des familles de langages issus de la [[hiérarchie de Chomsky]]'''
!
![[Langage rationnel|Langages<br> rationnels]]
![[Langage algébrique#Langages déterministes|Langages algébriques<br> déterministes]]
![[Langage algébrique|Langages<br> algébriques]]
![[Langage contextuel|Langages<br> contextuels]]
![[Langage récursif|Langages<br> récursifs]]
![[Récursivement énumérable|Langages récursivement<br> énumérables]]
|-align="center"
![[Opération ensembliste|Union]]
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
![[Opération ensembliste|Intersection]]
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
![[Complémentaire (théorie des ensembles)|Complémentaire]]
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|-align="center"
![[Concaténation]]
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
![[Étoile de Kleene|Etoile de Kleene]]
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
![[Mot (mathématiques)|Miroir]]
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
!Mélange<ref>Preuves dans {{Article|langue=en| auteur1 = [[Zoltán Ésik]] | auteur2 = [[Imre Simon]]| titre = Modeling literal morphisms by shuffle| journal = [[Semigroup Forum]]| volume = 56| année = 1998| pages= 225-227}}.</ref>
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#fdd"|Pas de clôture
|style="background:#fdd"|Pas de clôture
|style="background:#fdd"|Pas de clôture
|style="background:#fdd"|Pas de clôture
|-align="center"
!Morphisme
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|-align="center"
!Morphisme croissant
|style="background:#dfd"|Clos
|style="background:#fdd"|Pas de clôture
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
!Morphisme inverse
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|style="background:#dfd"|Clos
|-align="center"
|}

== Notes et références ==
{{Références}}

== Voir aussi ==
{{Autres projets
  | wikiversity = Théorie des langages
  | wikiversity titre = Théorie des langages
  | commons = Category:Formal languages
}}
=== Bibliographie ===
* {{Ouvrage| langue=fr| prénom1=Olivier| nom1=Carton| titre=Langages formels, calculabilité et complexité| lieu=Paris| éditeur=[[Vuibert]]| collection=Capes-agrég| année=2008| mois=10| jour=28| numéro d'édition=1| pages totales=240| format=17 x 24| isbn=978-2-7117-2077-4| isbn2=2-7117-2077-2| présentation en ligne=http://www.eyrolles.com/Sciences/Livre/langages-formels-calculabilite-et-complexite-9782711720774| lire en ligne=http://www.normalesup.org/~bisson/tea/lfcc.pdf| consulté le=16 juin2011}}

=== Articles connexes ===
{{début colonnes|taille=20}}
* [[Langage de programmation]]
* [[Étoile de Kleene]]
* [[Langage congruentiel]]
* [[Linguistique]]
* [[Noam Chomsky]]
* [[Marcel-Paul Schützenberger]]
* [[Centraliseur]]
* [[Transducteur fini]]
* [[Algèbre de mélange]]
* [[Morphisme]]
* [[Philosophie linguistique]]
* [[Système axiomatique]]
* [[Congruence de Simon]]
{{fin colonnes}}

=== Liens externes ===
{{Liens}}

{{Palette|Langages formels grammaires et automates|Informatique théorique}}
{{Portail|Informatique|Langues|Mathématiques|Informatique théorique}}

[[Catégorie:Langage formel| ]]
[[Catégorie:Linguistique informatique]]