Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Langage algébrique
Résumé
En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente, un langage algébrique est un langage reconnu par un automate à pile.
Les langages algébriques forment les langages de dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML.
Plusieurs équivalents sont employés et équivalents : langage « context-free » ou langage non contextuel, , langage acontextuel.
Les langages algébriques ont pour objectif de capturer une structure des mots qui consiste en des associations de symboles, typiquement représentées par des groupements de parenthèses ; ces mots et langages correspondent bien à des expressions structurées dans les langages de programmation (la structure begin - end, ou l'indentation) et se représentent aussi dans la hiérarchisation d'informations par des arbres, par exemple. Toutes ces possibilités dépassent les capacités d'un langage rationnel.
Le langage est l'exemple type d'un langage algébrique qui n'est pas un langage rationnel. Il est formé des mots qui ont autant de lettres que de lettres , et avec la condition supplémentaire que les lettres précèdent les lettres .
Les langages de Dyck (ce sont des langages de mots bien parenthésées) sont des langages algébriques.
Les expressions arithmétiques, utilisant les quatre opérations élémentaires, par exemple , etc., forment un langage algébrique. C'est d'ailleurs cette observation qui historiquement est à la base du développement des compilateurs qui doivent, entre autres, traduire des expressions arithmétiques complexes en les décomposant en opération élémentaires.
Pour prouver qu'un langage est algébrique, on donne une grammaire non contextuelle qui l'engendre. Voir le paragraphe d'exemples de l'article en question pour plus de détails.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.