Langage formel, Alphabet d'un langage formel, ensemble des symboles, lettres ou lexèmes, théorie des langages formels, mots bien formés ou formules bien formées, grammaire formelle et algébriques et analysé par des automates, phrase Colorless green ideas sleep furiously.
Dans la logique 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. Dans la 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. Dans une 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.
Architectures des langages formels
- Grammaires formelles, mots sont produits par des règles, en nombre fini, qui s'appliquent dans des conditions précises.
- Expressions rationnelles, mots sont décrits selon pour décrire des successions, des répétitions, des alternatives.
- Automates, ce sont des objets mathématiques qui reconnaissent (dans un sens mathématique donné)
- Ensemble des instances d'un problème de décision dont la réponse est OUI ;
- Divers systèmes logiques de description à l'aide de formules logiques.
- Systèmes de réécriture. Une famille particulière est formée des langages congruents.
Appartenances de calculabilités et complexités
- Peut-on décider par algorithme si un mot donné appartient à ce langage ?
- Si oui, quelle est la complexité algorithmique d'une telle réponse ?
Type de grammaire générant une famille de langage.
- Les grammaires de type 0 génèrent la famille des langages récursivement énumérables.
- Les grammaires de type 1 génèrent la famille des langages contextuels.
- Les grammaires de type 2 génèrent la famille des langages algébriques.
- Les grammaires de type 3 génèrent la famille des langages rationnels.
