Langage formel

Cet article concerne les langages formels en informatique. Pour d'autres usages, voir Formalisation (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'é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. Elle est corrélée à la théorie de la calculabilité.

La théorie des langages s'applique en particulier dans la réalisation des compilateurs de langages de programmation.

Mots

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₁,a₂,...,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 ε.
• 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

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 {a, b},
• l'ensemble des mots de la forme aⁿ, 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

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 grammaires formelles. Les mots sont produits par des règles, en nombre fini, qui s'appliquent dans des conditions précises (voir Hiérarchie de Chomsky);
• les 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 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, les machine de Turing ou les automates finis;
• l'ensemble des instances d'un problème de décision dont la réponse est OUI;
• divers systèmes logiques de description à l'aide de formules logiques.

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

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.

• Les opération ensemblistes intersection, union et complémentation sont définis comme pour tous ensembles.
• La concaténation de L et de M, notée simplement LM est l'ensemble des mots de la forme xy où x 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 à 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 miroir 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_n$ où $n\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 {ab} Ш {ba} = {abba,baab,baba}.

Notes et références

• Cet article est partiellement ou en totalité issu de l'article intitulé « Théorie des langages » (voir la liste des auteurs).
• Olivier Carton, Langages formels, calculabilité et complexité, Paris, Vuibert, coll. « Capes-agrég », 28 octobre 2008, 1^re éd., 17 x 24, 240 p. (ISBN 978-2-7117-2077-4 et 2-7117-2077-2) [lire en ligne (page consultée le 16 juin2011)] [présentation en ligne] 

Voir aussi

• Langage formel mathématique
• Langage de programmation
• Grammaire formelle
• Automate fini
• Fermeture de Kleene
• Hiérarchie de Chomsky
• Langage régulier
• Linguistique

• Noam Chomsky
• Marcel-Paul Schützenberger