Théorie des langages

Infos
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
Théorie des langages

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).
- \displaystyle X^k=\underbrace_k\, fois est l'ensemble des mots de longueur k
- X^
-=\bigcup_k \in \mathbb X^k\, est l'ensemble des mots.
- \epsilon ou est le mot vide de longueur 0.
- On définit sur X^
-\, , 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)\, (de longueur n+m). Cette loi de composition interne est associative et admet le mot vide pour élément neutre, par conséquent \langle X^
-, \cdot, \epsilon \rangle\, est un monoïde, appelé monoïde libre sur X\, . 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\,

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, par exemple :
- les langages rationnels peuvent être décrits par des automates finis ou des expressions rationnelles ;
- les langages algébriques peuvent être décrits par des grammaires hors-contexte ou des automates à piles ;
- ...

Voir aussi

- Automate fini
- Fermeture de Kleene
- Grammaire formelle
- Hiérarchie de Chomsky
- Langage formel
- Langage régulier
- Linguistique
-Noam Chomsky
-Marcel-Paul Schützenberger Catégorie:Langage formel Langages
Sujets connexes
Alphabet   Automate fini   Automate à pile   Compilateur   Concaténation   Expression rationnelle   Fermeture de Kleene   Grammaire   Grammaire formelle   Hiérarchie de Chomsky   Informatique   Langage   Langage formel   Langage rationnel   Lexème   Linguistique   Loi de composition interne   Marcel-Paul Schützenberger   Mathématiques   Monoïde   Mot   N-uplet   Noam Chomsky   Système de transition d'états  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^