THéorie des Langages

La théorie des langages formels constitue une base de l'informatique théorique. Cependant, son origine et sa motivation proviennent de différentes sources:

• Les circuits de commande en tant que modèles pour les ingénieurs électriciens.

• Les grammaires comme modèles pour la structure des langues naturelles (Chomsky, 1956).
• Les modèles de phénomènes biologiques: les réseaux neuronaux qui ont conduit aux automates finis (McCulloh & Pitts, 1943).

• Les modèles dans les différentes parties de la théorie des langages de programmation: l'analyse, la compilation, l'édition de texte,. . .

• Les modèles pour les problèmes mathématiques (et philosophiques) de calculabilité (Turing, 1936).

La liste ci-dessus donne également des exemples d'applications des langages formels. D'autres domaines d'application plus récents sont la cryptographie et l'infographie.

Dans ce cours, nous nous concentrons sur les langages plus exactement les langages réguliers et les langages hors contexte.