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.