Langages formels

Un langage formel est une sorte de généralisation de la notion de langage à laquelle nous sommes habitués dans la vie courante.

Notions de base

Pour commencer, imaginons un langage formel comme une langue ordinaire, par exemple le français. De quoi se compose une telle langue ? Elle se compose de mots, que nous assemblons ensuite en phrases. Les phrases ne nous intéresseront pas, seuls les mots comptent. De quoi se composent les mots ? Des lettres de l’alphabet. Nous commençons donc par l’alphabet.

Un alphabet est un ensemble quelconque non vide. Les éléments de l’alphabet s’appellent des symboles. S’il s’agit du français, ce sera l’alphabet usuel comprenant les minuscules comme les majuscules, ainsi que les variantes de lettres avec accents, tréma et cédille. Si nous ne voulions pas décrire le français, mais par exemple des nombres, l’alphabet contiendrait les dix chiffres. L’alphabet est souvent noté par le symbole Σ.

Un mot, ou encore une chaîne de caractères, est une suite finie de symboles d’un alphabet Σ. Si nous avons par exemple l’alphabet Σ= {a ; b ; c ; d ; e ; … ; z}, alors « salut » ou « doberman » sont des mots, mais pas « soirée » (la lettre « é » n’est pas dans l’alphabet), « Hugo » (la lettre « H » n’y est pas) ni « bonne nuit » (il n’y a pas d’espace). La longueur d’un mot est le nombre de symboles dont il se compose.

Concaténation de mots : si nous avons deux mots a = a₁a₂… a_n et b = b₁b₂… b_m, alors leur concaténation est le mot ab = a₁a₂… a_nb₁b₂… b_m. Exemple : en concaténant les mots « salut » et « doberman », on obtient le mot « salutdoberman ». On note la concaténation soit par un petit rond, c’est-à-dire a ∘ b, soit par aucun signe : on écrit simplement les mots l’un après l’autre, sans symbole particulier.

Le mot vide se note ε ; c’est le mot de longueur zéro. Si nous concaténons un mot a = a₁… a_n avec le mot vide ε, nous retrouvons le mot a. Autrement dit, a ∘ ε = a.

L’ensemble Σ^∗ de tous les mots sur l’alphabet Σ (l’étoile de Kleene) est l’ensemble de tous les mots que nous pouvons former avec l’alphabet Σ, mot vide compris. On le note Σ^∗. Pour l’alphabet binaire Σ= {0 ; 1}, on a

$Σ^{*} = {ε; 0; 1; 00; 01; 10; 11; 000; 001; \dots}$

On utilise parfois aussi la fermeture positive de l’alphabet, c’est-à-dire de nouveau tous les mots que nous pouvons former avec l’alphabet, sauf le mot vide. On la note Σ⁺ et l’on a Σ⁺ = Σ^∗ ∖ {ε}.

Exemples d’alphabets

Revenons à l’exemple du français. Chaque mot français se trouve dans l’ensemble de tous les mots sur l’alphabet qui contient les minuscules, les majuscules et les variantes avec signes diacritiques (et peut-être aussi le trait d’union « - » et l’apostrophe). Si nous ajoutons à cet alphabet l’espace et les signes de ponctuation (virgule, point, point d’exclamation, point d’interrogation, …), cet ensemble contient toutes les phrases que nous sommes capables de former en français. Bien sûr, il contiendra aussi des phrases du genre « sadflsf kasdf kagrjewàiâçérôker kf fkjbsjbgvbadfgsa !!! :?? : ::!?:?:sdf », qui restent pourtant plus sensées que bien des commentaires lus sur Internet.
Si notre alphabet contient tous les chiffres Σ= {0 ; 1 ; … ; 9}, l’ensemble de tous les mots contiendra tous les entiers naturels, et même quelques autres mots. Il y aura en effet aussi des mots commençant par un zéro, par exemple 00054, ou le zéro seul, et de plus le mot vide, qui n’est évidemment pas un nombre.
L’alphabet doit être non vide, donc le plus petit alphabet a au moins un symbole. Par exemple, pour l’alphabet Σ= {!}, nous obtiendrions Σ^∗ = {ε ; ! ; !! ; !!! ; !!!! ; …}, c’est-à-dire un ensemble de mots où, pour chaque n ∈ ℕ, il existe un mot qui a n points d’exclamation et aucun autre mot n’appartient à l’ensemble.
Soit Σ= {qw ; c}. C’est un alphabet très étrange, car il contient le mot qw. Cette notation n’est généralement pas utilisée, parce qu’elle est confuse et bizarre, mais on peut se représenter les choses ainsi : nous collons les lettres « q » et « w » l’une à l’autre de sorte qu’elles forment un seul caractère. Nous pouvons alors voir le mot « qw » comme le symbole « qw ». Si nous formions avec ces symboles le mot « qwcqw », ce mot aurait une longueur de trois : il serait composé des symboles « qw », « c » et « qw ». On ne rencontre pas très souvent de tels alphabets, mais il existe des situations où nous avons besoin d’utiliser des symboles composés de plusieurs symboles.

Langage formel

Un langage (formel) sur un alphabet Σ est une partie quelconque de Σ^∗. Pour un langage L sur l’alphabet Σ, on a donc L ⊆ Σ^∗. Exemples de langages :

Dans la partie précédente, nous avons défini l’alphabet des chiffres Σ= {0 ; 1 ; … ; 9}. L’ensemble de tous les mots est formé de tous les mots composés uniquement de chiffres. Si nous ajoutons la règle qu’un mot ne doit pas commencer par zéro et ne doit pas être vide, nous obtenons l’ensemble des entiers naturels non nuls ℕ^*. On a la relation ℕ^* ⊆ Σ^∗, donc ℕ^* est un langage sur l’alphabet Σ.
À l’ensemble de chiffres précédent, nous pouvons encore ajouter le signe moins « - », donc Σ= {0 ; 1 ; … ; 9 ; −}. L’ensemble de tous les mots est alors formé de tous les mots composés de chiffres ou du signe moins. Cela signifie toutefois qu’il contient aussi des mots comme « 12-84- », « 1-5-8 » ou « - ». Nous obtenons le langage des entiers relatifs ℤ en ajoutant trois règles :
- Le signe moins n’apparaît pas du tout dans le mot ou n’apparaît qu’au début du mot.
- Le premier chiffre du mot ne peut pas être zéro, sauf pour le mot « 0 ».
- Chaque mot doit contenir au moins un chiffre.
Cet ensemble décrit l’ensemble des entiers relatifs et c’est une partie de l’ensemble Σ^∗ ; c’est donc un langage sur l’alphabet Σ.
Soit Σ= {0 ; 1}. L’ensemble de tous les mots est formé de tous les mots composés de zéros et de uns. Nous pouvons définir un langage L sur cet alphabet, par exemple, comme l’ensemble de tous les mots qui ont exactement trois uns. Nous pouvons aussi être plus créatifs et dire que le langage L sera l’ensemble de tous les mots qui représentent un format de fichier docx valide (ce qui sort de Word).
Restons sur l’alphabet binaire Σ= {0 ; 1}. Toute chaîne de caractères (des caractères usuels, ceux de votre clavier) peut être convertie en écriture binaire, c’est-à-dire en zéros et en uns, puis reconvertie, par exemple à l’aide de la table ASCII (ou plus exactement : la table ASCII fait correspondre des nombres aux caractères, et les nombres du système décimal peuvent être convertis en système binaire). Nous pouvons ainsi définir le langage de tous les mots qui correspondent à une adresse e-mail valide, et ce sera encore un langage sur l’alphabet binaire.

Concaténation de langages : nous pouvons aussi concaténer des langages. La définition ressemble à celle du produit cartésien d’ensembles. Soit deux langages L₁ et L₂. Leur concaténation L₁ ∘ L₂ est un nouveau langage défini ainsi :

$L_{1} \circ L_{2} = {w_{1} \circ w_{2} | w_{1} \in L_{1}, w_{2} \in L_{2}}$

Autrement dit, nous prenons tous les mots du langage L₁ et nous les concaténons avec tous les mots du langage L₂. Exemple : soit

$\begin{array}{rcl} L_{1} & = & {0; 1} \\ L_{2} & = & {a; b; s a l u t} \end{array}$

Alors

$\begin{array}{rcl} L_{1} \circ L_{2} & = & {0 a; 0 b; 0 s a l u t; 1 a; 1 b; 1 s a l u t} \\ L_{2} \circ L_{1} & = & {a 0; a 1; b 0; b 1; s a l u t 0; s a l u t 1} \\ L_{1} \circ L_{1} & = & {00; 01; 10; 11} \end{array}$

Jusqu’ici, pour décrire des langages, nous avons utilisé le langage courant : nous avons simplement décrit en mots à quoi le langage doit ressembler. C’est très peu pratique, c’est pourquoi on introduit une manière plus formelle de définir un langage. La première est la grammaire.

« Précédent: Informatique

Suivant: Automates finis »