Langage formel

Un langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. La théorie des langages formels a pour objectif de décrire les langages formels. Les mots sont des suites d'éléments de cet alphabet ; les mots qui appartiennent à un langage formel particulier sont parfois appelés mots bien formés ou formules bien formées. Un langage formel est souvent défini par une grammaire formelle, telle que les grammaires algébriques et analysé par des automates. La théorie des langages formels étudie les aspects purement syntaxiques de tels langages, c'est-à-dire leur structure interne formelle. La théorie des langues est issue de la linguistique, comme moyen de comprendre les régularités syntaxiques de langues naturelles : En informatique, les langages formels sont souvent utilisés comme base pour la définition des langages de programmation et d'autres systèmes ; les mots d'un langage comportent alors aussi un sens, une sémantique. En théorie de la complexité des algorithmes, les problèmes de décision sont généralement définis comme des langages formels, et les classes de complexité sont définies comme les ensembles de langages formels qui peuvent être analysés par des machines ayant des ressources de calcul limitées. En logique mathématique, les langages formels sont utilisés pour représenter la syntaxe des systèmes axiomatiques, et l'attitude formaliste en mathématique ou logicisme affirme qu'en principe, les mathématiques peuvent se ramener à la manipulation syntaxique de langages formels. L'étude des langages formels comporte l'ensemble des moyens de description et d'analyse de ces langages, comme les grammaires formelles pour la génération et les automates pour la reconnaissance, mais elle s'intéresse aussi à l'apprentissage automatique et la traduction automatique des langages.

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

Publications associées (3)

Personnes associées (2)

Concepts associés (173)

Cours associés (13)

Séances de cours associées (151)

Computational Design of Steady 3D Dissection Puzzles

Bailin Deng, Peng Song, Xiaofei Wang

Dissection puzzles require assembling a common set of pieces into multiple distinct forms. Existing works focus on creating 2D dissection puzzles that form primitive or naturalistic shapes. Unlike 2D

WILEY2019

Security protocols are essential to the proper functioning of any distributed system running over an insecure network but often have flaws that can be exploited even without breaking the cryptography.

EPFL2008

Formal Modelling of Objects and Subsystems in an Information Systems Framework

IOS Press1994

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

CS-452: Foundations of software

The course introduces the foundations on which programs and programming languages are built. It introduces syntax, types and semantics as building blocks that together define the properties of a progr

HUM-224: Graphic design B

Le cours vise à faire découvrir les bases du design graphique, ses enjeux, ses différents domaines d'application, ses techniques et ses conventions. Il s'agit d'un enseignement pratique qui repose sur

Logique

La logique — du grec , qui est un terme dérivé de signifiant à la fois « raison », « langage » et « raisonnement » — est, dans une première approche, l'étude de l'inférence, c'est-à-dire des règles formelles que doit respecter toute argumentation correcte. Le terme aurait été utilisé pour la première fois par Xénocrate. La logique antique se décompose d'abord en dialectique et rhétorique. Elle est depuis l'Antiquité l'une des grandes disciplines de la philosophie, avec l'éthique (philosophie morale) et la physique (science de la nature).

Hiérarchie de Chomsky

vignette|Hiérarchie de Chomsky. En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. La hiérarchie introduite par Noam Chomsky repose sur le modèle de grammaire formelle.

Langage contextuel

En informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context-sensitive language) est un langage formel engendré par une grammaire contextuelle. C'est un langage de type 1 dans la hiérarchie de Chomsky. Les langages contextuels sont les langages reconnus par les automates linéairement bornés, c'est-à-dire les machines de Turing dont la mémoire de travail est linéairement bornée en fonction de la taille de l'entrée.

Couvre les fondamentaux des automates finis et des langues formelles.

Couvre les bases des langues formelles, y compris les alphabets, les mots et les langues, ainsi que des opérations comme la concaténation et l'inversion.

Introduit des expressions régulières, couvrant les ensembles de langage, la syntaxe, la sémantique et les limitations.