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.

Définition formelle 

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.

Propriétés 

 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). Les monoïdes  sont donc des sous-monoïdes libres.
 Les langages de Dyck et les langages de Dyck premiers sont des langages algébriques déterministes. Voici une grammaire :        La variable  engendre le langage de Dyck , la variable  engendre le langage des mots Dyck premiers .
 Une autre grammaire fréquemment rencontrée est :        La variable  engendre le langage de Dyck , mais la grammaire est ambiguë.
 Le théorème de Chomsky–Schützenberger énonce que tout langage algébrique est une image homomorphe de l'intersection d'un langage de Dyck avec un langage rationnel.
 Ce théorème peut être affiné comme suit : tout langage algébrique  est une image homomorphe de l'intersection d'un langage rationnel et de l'image homomorphe inverse du langage de Dyck sur deux paires de parenthèses:        où  et  sont des morphismes et  est un langage rationnel.
 De manière équivalente, cet énoncé signifie que tout langage algébrique est image de  par une transduction rationnelle, ou encore que le langage  est un générateur du cône rationnel des langages algébriques.
 Le langage de Dyck sur deux paires de parenthèses appartient à la classe de complexité .
 Les mots de Dyck ont de nombreuses propriétés et caractérisations combinatoires. Le nombre de mots de Dyck sur une paire de parenthèses de longueur  est égal au nombre de Catalan .
 Le monoïde syntaxique du langage de Dyck est le monoïde bicyclique.

Langages de Dyck bilatères 
Intuitivement, un mot de Dyck bilatère est un mot bien formé de symboles et de leurs inverses qui se simplifient lorsqu'ils se trouvent adjacents, comme  dans un groupe. Ici, on utilise plutôt  pour symboliser l’inverse de la lettre .
Les langages de Dyck bilatères, formés de mots de Dyck bilatères, sont reliés à la définition des groupes libres.

Soit  un alphabet, et soit  une copie de  disjointe de . Ici, la copie  de la lettre  est vue comme son inverse formelle.
Sur l'ensemble  des mots sur , on définit une relation de réduction comme suit :

 s'il existe une factorisation  ou  telle que , avec . La réduction de Dyck bilatère est la fermeture transitive de cette relation.

Par exemple, on a

Un mot de Dyck bilatère est un mot qui se réduit au mot vide . La relation de réécriture définie ci-dessus est confluente, et tout mot se réduit en un mot irréductible (c'est-à-dire ne contenant aucun facteur
 ou ) unique. L'ensemble des mots irréductibles est un langage rationnel. Il est en bijection avec le groupe libre sur .

Le langage de Dyck bilatère sur  est l'ensemble des mots de Dyck bilatères.

Propriétés 

 Les langages de Dyck bilatères sont algébriques. Voici une grammaire :

Cette grammaire est ambiguë. Par exemple, le mot  a les deux dérivations gauches suivantes :

Il existe des grammaires non ambiguës pour les langages de Dyck bilatères. En voici une :

Dans le cas où l'alphabet  est composé d'une seule lettre , cette grammaire se réduit à :

 Le théorème de Chomsky–Schützenberger reste valable lorsque les langages de Dyck sont remplacés par les langages de Dyck bilatères.

Références

Notes et références

Articles connexes 
 Grammaire formelle
 Hiérarchie de Chomsky
 Monoïde syntaxique
 Noam Chomsky
 Marcel-Paul Schützenberger
 Nombre de Catalan

Dyck