- Théorie des langages
-
En informatique, la théorie des langages a pour objectif de décrire les langages formels, vus comme moyen de communication, d'un point de vue mathématique.
Un langage formel[1] est un ensemble de mots. Un mot est une suite finie de symboles. L'ensemble de ces symboles est appelé alphabet, les symboles eux-mêmes sont des lettres.
Un langage (formel) doit pouvoir être décrit et analysé par une méthode formelle. Plusieurs sortes de mécanismes peuvent exister:
- Une description au moyen d'une grammaire formelle, permettant d'engendrer les mots du langage,
- Un dispositif d'analyse reconnaissant les mots du langage. Ce sont des automates. Les automates finis reconnaissent les langages rationnels, les automates à pile reconnaissent les langages algébriques, des automates plus sophistiqués existent pour d'autres classes de langages.
- Une description au moyen d'une formule logique
La théorie des langages s'applique en particulier dans la réalisation des compilateurs.
Mots
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 = (a1,a2,...,ak) de k lettres.
- L'ensemble des mots sur l'alphabet A est noté A * .
- Le mot vide, de longueur 0, est noté ε.
- On définit sur A * , une loi de composition interne appelée concaténation. Elle associe à deux mots (a1,...,an) et (b1,...,bm) le mot
(a1,...,an,b1,...,bm) (de longueur n + m). Cette loi de composition interne est associative et admet le mot vide pour élément neutre, par conséquent A * , muni de cette loi, est un monoïde. C'est un monoïde libre au sens de l'algèbre.
Voir aussi
- Automate fini
- Fermeture de Kleene
- Grammaire formelle
- Hiérarchie de Chomsky
- Langage formel
- Langage régulier
- Linguistique
- Une fois qu'il est acquis que l'on parle de langage formel, on utilise alors le substantif « langage » sans l'adjectif « formel ».
Wikimedia Foundation. 2010.
