Ouvrir le menu principal

Wikipédia β

Langage formel

ensemble de chaînes de symboles contraintes par des règles
Page d'aide sur l'homonymie Cet article concerne les langages formels en informatique. Pour d'autres usages, voir Formalisation (mathématiques).

En mathématiques, en informatique et en linguistique, la théorie des langages a pour objectif de décrire les langages formels. Un langage formel est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini.

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 formules bien formées. Un langage formel est souvent défini par une grammaire formelle, telle que les grammaires algébriques et analysé par des automates.

La théorie des langages étudie les aspects purement 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 langues naturelles. En informatique, les langages formels sont souvent utilisés comme base pour la définition des 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èmes de décision sont généralement définis comme des langages formels, et les 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èmes axiomatiques, et l'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 grammaires formelles pour la génération et les automates pour la reconnaissance, mais elle s'intéresse aussi à l'apprentissage (en) des langages et à leur traduction. Dans le domaine de la traduction, la théorie des langages s'applique aux compilateurs de langages de programmation.

Sommaire

MotsModifier

Article détaillé : Mot (mathématiques).

On se donne un ensemble  , appelé alphabet dont les éléments sont appelés des lettres.

  • Un mot de longueur k est une suite   de k lettres. En pratique, on utilise la notation condensée  .
  • L'ensemble des mots sur l'alphabet   est noté  .
  • Le mot vide, de longueur 0, est noté  , ou parfois   (ou encore   pour le distinguer des  -transitions dans les automates finis).
  • On définit sur  , une loi de composition interne appelée concaténation. Elle associe à deux mots   et   le mot   (de longueur  ).

Cette loi de composition interne est associative et admet le mot vide pour élément neutre (ce qui justifie la notation  ). Par conséquent l'ensemble  , muni de cette loi, est un monoïde. C'est un monoïde libre au sens de l'algèbre.

Langages formelsModifier

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

ExemplesModifier

Quelques exemples de langages formels :

  • l'ensemble de tous les mots sur  ,
  • l'ensemble des mots de la forme  , où   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 formelModifier

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 :

Appartenance, calculabilité et complexitéModifier

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

Familles de langagesModifier

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.

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 algébrique, qui est lui-même 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 leur propriétés. Les langages algébriques déterministes sont les langages reconnaissables par les automates à pile déterministes, et sont donc strictement inclus dans la famille des langages algébriques. Les 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 langages récursivement énumérables.

Opérations sur les langages formelsModifier

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 ensemblistesModifier

Les opérations ensemblistes intersection, union et complémentation sont définis comme pour tout ensemble.

Concaténation ou produitModifier

La concaténation de L et de M, notée simplement   est l'ensemble des mots de la forme xyx est un mot de L et y est un mot de M.

Quotients ou résiduelsModifier

Le quotient à gauche   de   par un mot   est l'ensemble des mots   tels que   appartient à  . Le quotient à gauche est aussi appelé résiduel.

Le quotient à droite   de   par un mot   est défini symétriquement comme l'ensemble des mots   tels que   appartient à  .

Le quotient à gauche et le quotient à droite s'étendent aux langages. Ainsi, le quotient à gauche de   par un langage  , noté  , est la réunion des langages   pour   dans  .

Étoile de KleeneModifier

L'étoile de Kleene de L est l'ensemble noté   composé des mots de la forme   avec   et  . Cet ensemble contient le mot vide.

Retourné ou image miroirModifier

Le renversé de L, noté   ou   contient les mots miroirs des mots de L, c'est-à-dire les mots de L lus de droite à gauche.

Mélange ou « shuffle »Modifier

Le mélange de L et M, noté L Ш M, est l'ensemble des mots pouvant s'écrire    et   sont des mots (éventuellement vides) tels que   soit un mot de L et   soit un mot de M. Par exemple[1]   Ш  .

Morphisme et morphisme inverseModifier

Une application   est un morphisme ou homomorphisme si   pour tous mots   de  . L'image homomorphe d'un langage   sur   est l'ensemble

 .

Par abus de langage, on appelle morphisme inverse l'inverse d'un morphisme. Le morphisme inverse de   est la fonction notée   de   dans l'ensemble des parties de   définie par

 .

Ce n'est en général pas un morphisme. L'image par un morphisme inverse d'un langage   sur   est le langage

 .

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ôtureModifier

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.

Tableau des propriétés de clôture[2] des familles de langages issus de la hiérarchie de Chomsky
Langages
rationnels
Langages algébriques
déterministes
Langages
algébriques
Langages
contextuels
Langages
récursifs
Langages récursivement
énumérables
Union Clos Pas de clôture Clos Clos Clos Clos
Intersection Clos Pas de clôture Pas de clôture Clos Clos Clos
Complémentaire Clos Clos Pas de clôture Clos Clos Pas de clôture
Concaténation Clos Pas de clôture Clos Clos Clos Clos
Etoile de Kleene Clos Pas de clôture Clos Clos Clos Clos
Miroir Clos Pas de clôture Clos Clos Clos Clos
Mélange[3] Clos Pas de clôture Pas de clôture Pas de clôture Pas de clôture Pas de clôture
Morphisme Clos Pas de clôture Clos Pas de clôture Pas de clôture Clos
Morphisme croissant Clos Pas de clôture Clos Clos Clos Clos
Morphisme inverse Clos Clos Clos Clos Clos Clos

Notes et référencesModifier

  1. Pour bien comprendre cet exemple, on écrit les lettres du deuxième mot en majuscules. Alors on obtient :
      Ш  
    et quand on remplace les majuscules par les minuscules, on a bien les mots indiqués.
  2. Preuves dans Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
  3. Preuves dans (en) Zoltán Ésik et Imre Simon, « Modeling literal morphisms by shuffle », Semigroup Forum, vol. 56,‎ , p. 225-227

Voir aussiModifier

Sur les autres projets Wikimedia :