Langage de Dyck

En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l'ensemble des mots bien parenthésés, sur un alphabet fini de parenthèses ouvrantes et fermantes. Par exemple, sur la paire de parenthèses formée de '(' et ')', le mot '(())()' est un mot bien parenthésé, alors que le mot '())(' ne l'est pas.

Les langages de Dyck jouent un rôle important en informatique théorique pour caractériser les langages algébriques. Le théorème de Chomsky Schützenberger énonce en effet que tout langage algébrique est l'image par un morphisme alphabétique de l'intersection d'un langage de Dyck avec un langage rationnel.

Les langages de Dyck ont été nommés ainsi d'après le mathématicien allemand Walther von Dyck.