Langage formel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections 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 particuliers 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 le formalisme mathématique veut qu'en principe les mathématiques pourraient 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. La théorie des langages s'applique en particulier dans la réalisation des compilateurs de langages de programmation.

Mots[modifier | modifier le code]

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

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

  • Un mot de longueur k est une suite u=(a_1,a_2,...,a_k) de k lettres. En pratique, on utilise la notation condensée u= a_1a_2\cdots a_k.
  • L'ensemble des mots sur l'alphabet A est noté A^*.
  • Le mot vide, de longueur 0, est noté 1, ou parfois \varepsilon.
  • On définit sur A^*, une loi de composition interne appelée concaténation. Elle associe à deux mots a_1 \cdots a_n et b_1 \cdots b_m le mot a_1 \cdots a_nb_1 \cdots b_m (de longueur n+m).

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

Langages formels[modifier | modifier le code]

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[modifier | modifier le code]

Quelques exemples de langages formels :

  • l'ensemble de tous les mots sur {a, b},
  • l'ensemble des mots de la forme a^n, où 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,
  • l'ensemble des 1000 mots les plus fréquents dans une langue donnée.

Construction d'un langage formel[modifier | modifier le code]

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 | modifier le code]

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

Opérations sur les langages formels[modifier | modifier le code]

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.

  • Les opérations ensemblistes intersection, union et complémentation sont définis comme pour tout ensemble.
  • La concaténation de L et de M, notée simplement LM est l'ensemble des mots de la forme xyx est un mot de L et y est un mot de M.
  • Le quotient à gauche de x^{-1}L de L par un mot x est l'ensemble des mots y tels que xy appartient à L. Le quotient à gauche est aussi appelé résiduel.
  • Le quotient à droite de Lx^{-1} de L par un mot x est défini symétriquement comme l'ensemble des mots y tels que yx appartient à L.
  • Le quotient à gauche et le quotient à droite s'étendent aux langages. Ainsi, le quotient à gauche de L par un langage M, noté M^{-1}L, est la réunion des langages x^{-1}L pour x dans M.
  • La fermeture de Kleene (ou étoile) de L est l'ensemble noté L^\star composé des mots de la forme u_1, u_2, \dots, u_n avec n\geqslant 0 et u_1, u_2, \dots, u_n \in L. Cet ensemble contient le mot vide.
  • Le renversé de L, noté L^R ou \tilde L contient les mots miroirs des mots de L, c'est-à-dire les mots de L lus de droite à gauche.
  • Le mélange de L et M, noté L Ш M, est l'ensemble des mots pouvant s'écrire u_1 v_1u_2 v_2 \dots u_n v_nn\geqslant 0 et u_1, \dots, u_n, v_1, \dots, v_n sont des mots (éventuellement vides) tels que u_1 u_2 \dots u_n soit un mot de L et v_1 v_2 \dots v_n soit un mot de M. Par exemple[1] \{ab\} Ш \{ba\} = \{abba, baab, baba, abab\}.

Notes et références[modifier | modifier le code]

  1. Pour bien comprendre cet exemple, on écrit les lettres du deuxième mot en majuscules. Alors on obtient :
    \{ab\} Ш \{BA\} = \{abBA, aBbA, BAab, BaAb, BabA, aBAb\}
    et quand on remplace les majuscules par les minuscules, on a bien les mots indiqués.

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :