De Turing à Chomsky : langues, langages,machines et monoïdes

DE TURING À CHOMSKY : LANGUES, LANGAGES, MACHINES ET MONOÏDES

Résumé :
La notion de machine de Turing peut être vue comme une manière de décrire un langage. (En mathématiques, les langages sont définis comme des sous-ensembles du monoïde libre sur un alphabet.) Mais reconnaître si un mot appartient au langage défini par une machine de Turing est un problème complexe. La recherche en langages formels s'est attachée à trouver des classes de langages plus simples mais encore adaptés aux langages du monde réel (langages de programmation, langues naturelles, etc.), par exemple les langages « rationnels » (ceux dont le monoïde syntaxique est fini, représentables par un automate fini) ou des langages hors-contexte (reconnaissables par un automate à pile). Il y a ainsi une hiérarchie des langages suivant la complexité de leur description, connue sous le nom de hiérarchie de Chomsky.