Définitions

On se donne un ensemble ${\displaystyle A}$, appelé alphabet dont les éléments sont appelés des lettres.

• Un mot de longueur k est une suite ${\displaystyle u=(a_{1},a_{2},...,a_{k})}$ de k lettres. En pratique, on utilise la notation condensée ${\displaystyle u=a_{1}a_{2}\cdots a_{k}}$.
• L'ensemble des mots sur l'alphabet ${\displaystyle A}$ est noté ${\displaystyle A^{*}}$.
• Le mot vide, de longueur ${\displaystyle 0}$, est noté ${\displaystyle 1}$, ou parfois ${\displaystyle \varepsilon }$ (ou encore ${\displaystyle \Lambda }$ pour le distinguer des ${\displaystyle \varepsilon }$-transitions dans les automates finis).
• On définit sur ${\displaystyle A^{*}}$, une loi de composition interne appelée concaténation. Elle associe à deux mots ${\displaystyle a_{1}\cdots a_{n}}$ et ${\displaystyle b_{1}\cdots b_{m}}$ le mot ${\displaystyle a_{1}\cdots a_{n}b_{1}\cdots b_{m}}$ (de longueur ${\displaystyle n+m}$).

Cette loi de composition interne est associative et admet le mot vide pour élément neutre (ce qui justifie la notation ${\displaystyle 1}$). Par conséquent l'ensemble ${\displaystyle A^{*}}$, muni de cette loi, est un monoïde. C'est un 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 ${\displaystyle \{a,b\}}$,
• l'ensemble des mots de la forme ${\displaystyle a^{n}}$, où ${\displaystyle 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. On obtient une classification de langages appelée 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èmes de transitions d'états, les machines 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.
• des systèmes de réécriture. Une famille particulière est formée des 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é.

Opérations ensemblistes

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

Concaténation ou produit

La concaténation de ${\displaystyle L}$ et de ${\displaystyle M}$, notée simplement ${\displaystyle LM}$ est l'ensemble des mots de la forme ${\displaystyle xy}$ où ${\displaystyle x}$ est un mot de ${\displaystyle L}$ et ${\displaystyle y}$ est un mot de ${\displaystyle M}$.

Quotients ou résiduels

Le quotient à gauche ${\displaystyle x^{-1}L}$ de ${\displaystyle L}$ par un mot ${\displaystyle x}$ est l'ensemble des mots ${\displaystyle y}$ tels que ${\displaystyle xy}$ appartient à ${\displaystyle L}$. Le quotient à gauche est aussi appelé résiduel.

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

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

Étoile de Kleene

L'étoile de Kleene de L est l'ensemble noté ${\displaystyle L^{\star }}$ composé des mots de la forme ${\displaystyle u_{1}.u_{2}.\dots .u_{n}}$ avec ${\displaystyle n\geqslant 0}$ et ${\displaystyle u_{1},u_{2},\dots ,u_{n}\in L}$. Cet ensemble contient le mot vide.

Retourné ou image miroir

Le renversé de L, noté ${\displaystyle L^{R}}$ ou ${\displaystyle {\tilde {L}}}$ contient les 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 ${\displaystyle u_{1}v_{1}u_{2}v_{2}\dots u_{n}v_{n}}$ où ${\displaystyle n\geqslant 0}$ et ${\displaystyle u_{1},\dots ,u_{n},v_{1},\dots ,v_{n}}$ sont des mots (éventuellement vides) tels que ${\displaystyle u_{1}u_{2}\dots u_{n}}$ soit un mot de L et ${\displaystyle v_{1}v_{2}\dots v_{n}}$ soit un mot de M. Par exemple^[2] ${\displaystyle \{ab\}}$ Ш ${\displaystyle \{ba\}=\{abba,baab,baba,abab\}}$.

Morphisme et morphisme inverse

Une application ${\displaystyle f:A^{*}\to B^{*}}$ est un morphisme ou homomorphisme si ${\displaystyle f(xy)=f(x)f(y)}$ pour tous mots ${\displaystyle x,y}$ de ${\displaystyle A^{*}}$. L'image homomorphe d'un langage ${\displaystyle L}$ sur ${\displaystyle A}$ est l'ensemble

${\displaystyle f(L)=\{f(x)\mid x\in L\}}$.

Par abus de langage, on appelle morphisme inverse l'inverse d'un morphisme. Le morphisme inverse de ${\displaystyle f:A^{*}\to B^{*}}$ est la fonction notée ${\displaystyle f^{-1}}$ de ${\displaystyle B^{*}}$ dans l'ensemble des parties de ${\displaystyle A^{*}}$ définie par

${\displaystyle f^{-1}(y)=\{x\in A^{*}\mid f(x)=y\}}$.

Ce n'est en général pas un morphisme. L'image par un morphisme inverse d'un langage ${\displaystyle M}$ sur ${\displaystyle B}$ est le langage

${\displaystyle f^{-1}(M)=\bigcup _{y\in M}f^{-1}(y)}$.

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.

Bibliographie

• Olivier Carton, Langages formels, calculabilité et complexité, Paris, Vuibert, coll. « Capes-agrég », 28 octobre 2008, 1^re éd., 240 p., 17 x 24 (ISBN 978-2-7117-2077-4 et 2-7117-2077-2, présentation en ligne, lire en ligne)

Articles connexes

Liens externes

• Notice dans un dictionnaire ou une encyclopédie généraliste :

  • Britannica
• Notices d'autorité :

  • BnF (données)
  • LCCN
  • GND
  • Japon
  • Israël
  • Tchéquie