Theorie des langages


Theorie des langages

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 = (a1,a2,...,ak).
  • \displaystyle X^k=\underbrace{X.X...X}_{k\, fois} est l'ensemble des mots de longueur k
  • X^*=\bigcup_{k \in \mathbb{N}} X^k\, est l'ensemble des mots.
  • ε 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 (a1,...,an) est égal au concaténé (a1).(a2)...(an). 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 :

Voir aussi

  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Th%C3%A9orie des langages ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Theorie des langages de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Théorie des langages — ● Théorie des langages étude mathématique et construction abstraite de langages formels …   Encyclopédie Universelle

  • 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… …   Wikipédia en Français

  • Théorie des langages et automates — 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… …   Wikipédia en Français

  • Theorie des types — Théorie des types La théorie des types est une branche de la logique mathématique qui a pour principales caractéristiques que tout objet (terme, fonction, ensemble) y a un type et que les entités ne peuvent se combiner qu en respectant des règles …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Théorie des expressions rationnelles — Langage rationnel Pour les articles homonymes, voir Langage, Régulier et Rationnel. Les expressions rationnelles permettent d engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les… …   Wikipédia en Français

  • Théorie des types — La théorie des types est une branche de la logique mathématique qui a pour principales caractéristiques que tout objet (terme, fonction, ensemble) y a un type et que les entités ne peuvent se combiner qu en respectant des règles de typage [1].… …   Wikipédia en Français

  • Theorie des automates — Théorie des automates Pour les articles homonymes, voir Théorie et Automate. La théorie des automates, intimement liée à l étude des langages formels, est une branche de l informatique théorique qui étudie la puissance de calcul de divers modèles …   Wikipédia en Français

  • Théorie des ensembles (usuelle) — Théorie naïve des ensembles Les ensembles sont d une importance fondamentale en mathématiques; en fait, de manière formelle, la mécanique interne des mathématiques (nombres, relations, fonctions, etc.) peut se définir en termes d ensembles. Il y… …   Wikipédia en Français

  • Theorie des automates finis — Théorie des automates finis Sommaire 1 Langages formels 1.1 Alphabet 1.2 Mot 2 Définitions 2.1 Automate fini …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.