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. Intuitivement, un mot est bien parenthésé, aussi appelé mot de Dyck, s'il peut être réduit au mot vide en supprimant successivement des paires adjacentes de parenthèses de même type. Par exemple, sur l'alphabet formé de , le mot est bien parenthésé parce que Donnons la définition formelle d'un mot de Dyck. Soit un alphabet, et soit une copie de disjointe de . Sur l'ensemble des mots sur , on définit la relation suivante : s'il existe une factorisation telle que , avec . La réduction de Dyck est la fermeture transitive de cette relation. Un mot de Dyck est un mot qui se réduit au mot vide . Le langage de Dyck sur est l'ensemble des mots de Dyck. La réduction de Dyck est un système de réécriture confluent. La congruence de Dyck est la fermeture réflexive, symétrique et transitive de la relation. La concaténation de deux mots de Dyck est encore un mot de Dyck, donc le langage de Dyck est un sous-monoïde du monoïde libre . Un mot Dyck premier est un mot de Dyck qui n'est pas une concaténation de plusieurs mots de Dyck. On note ou l'ensemble des mots Dyck premiers, et ou le langage de Dyck. On rencontre aussi la notation lorsque l'alphabet contient lettres. L'ensemble des mots de Dyck premiers est un code bifixe (c'est-à-dire un code préfixe et suffixe).