Langage formel | Théorie

La théorie des langages a pour objectif de comprendre le fonctionnement des langages, vus comme moyen de communication, d'un point de vue mathématique.

Un langage est un ensemble de mots. Un mot (ou lexème) est une combinaison de signes élémentaires. L'ensemble de ces signes élémentaires est appelé alphabet. La fonction associant l'alphabet au langage est appelée grammaire. On peut associer à une grammaire un automate permettant de déterminer si un mot fait partie d'un langage.

Parmi les applications pratiques de la théorie des langages, on trouve en particulier les compilateurs, en informatique

Mots

---

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

• Un mot de longueur k est un k-uplet de lettres $u=(a\_1,a\_2,...,a\_k)$.
• $X^k=\backslash underbrace\{X.X...X\}\_\{k\backslash ,\; fois\}$ est l'ensemble des mots de longueur k
• $X^*=\backslash bigcup\_\{k\; \backslash in\; \backslash mathbb\{N\}\}\; X^k\backslash ,$ est l'ensemble des mots.
• $\backslash epsilon$ ou () est le mot vide de longueur 0.
• On définit sur $X^*\backslash ,$, une loi de composition interne appelée concaténation.

$(a\_1,...,a\_n).(b\_1,...,b\_m)=(a\_1,...,a\_n,b\_1,...,b\_m)\backslash ,$ (de longueur $n+m$).

Cette loi de composition interne est associative et admet le mot vide pour élément neutre, par conséquent $\backslash langle\; X^*,\backslash cdot,\backslash epsilon\; \backslash rangle\backslash ,$ est un monoïde, appelé monoïde libre sur $X\backslash ,$.

Remarque: Tout mot $(a\_1,...,a\_n)$ est égal au concaténé $(a\_1).(a\_2)...(a\_n)$. En identifiant les mots de longueur 1 aux lettres, on écrit donc le mot sous la forme: $u=a\_1.a\_2...a\_n\backslash ,$

Langages

---

Un ensemble de mots sur X est appelé un langage. Les langages peuvent être caractérisés par les moyens qui permettent de les décrire

• Les langages rationnels peuvent être décrits par des automates finis
• les langages réguliers sont décrits par des expressions régulières (un théorème montre que les langages réguliers sont rationnels et vice versa).
• les langages algébriques peuvent être décrits par des grammaires context free ou des automates à piles
• ...

Voir aussi

• Linguistique
• Langage formel
• Fermeture de Kleene
• Automate fini