Théorie des langages et automates

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 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

Informatique théorique
Théorie du calcul
Calculabilité Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Récursivement énumérable
Modèle de calcul Automate fini • Automate cellulaire • Machine de Turing • Thèse de Church
Modes de calcul Concurrence • Parallèlisme • Théorie de l'ordonnancement
Mesure et échelle de complexité Réduction polynomiale • Problème NP-complet
Logique, syntaxe et sémantique
Logique mathématique Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types
Grammaire formelle et systèmes de réécriture Compilation • Expression rationnelle • Grammaire formelle • Langage rationnel • Théorie des langages
Sémantique Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle
Spécifier, vérifier et concevoir des programmes Interprétation abstraite • Méthodes formelles • Model checking
Algorithmique, complexité et mathématiques discrètes
Algorithmique Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique
Problèmes et algorithmes numériques Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité
Problèmes et algorithmes non-numériques Algorithmes de la théorie des graphes • Arbre (informatique) • Liste (informatique) • Table de hachage • Tas (informatique)
Théorie des graphes Coloration de graphe • Problèmes de cheminement
Recherche opérationnelle Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement
Données et codage Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information
  • 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 Théorie des langages et automates de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

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

  • 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 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

  • 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

  • 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

  • Théorie des automates — Pour les articles homonymes, voir Théorie et Automate. En informatique théorique, la théorie des automates est l étude de machines abstraites définissant un modèle de calcul[H 1]. Cette théorie est le fondement de branches très importantes de l… …   Wikipédia en Français

  • Théorie des automates finis — Article principal : Automate fini. Cet article décrit la théorie des automates finis, cas particulier de la théorie des automates. Sommaire 1 Langages formels 1.1 Alphabet 1.2 Mot …   Wikipédia en Français

  • Classification des langages — Hiérarchie de Chomsky La hiérarchie de Chomsky est une classification naturelle (non arbitraire) des langages décrits par les grammaires formelles, découverte en 1956 par le linguiste Noam Chomsky. Tout langage pouvant être généré ou accepté par… …   Wikipédia en Français

  • Semantique des langages de programmation — Sémantique des langages de programmation En informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques. Sommaire 1 Lien avec la… …   Wikipédia en Français

  • Sémantique des langages de programmation — En informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques. Sommaire 1 Lien avec la linguistique 2 Sémantiques usuelles d’un… …   Wikipédia en Français

Share the article and excerpts

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