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

modifier

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

modifier
  • 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:
           
    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é TC0 (en).
  • 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

modifier

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[1].

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

modifier
  • 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

modifier

Notes et références

modifier
  1. La terminologie « bilatère » n'est pas fréquente : en anglais, on utilise souvent « two-sided Dyck words ». Jacques Labelle (Annales des sciences mathématiques du Québec vol. 17, no 1, 1993) utilise expressément le terme « bilatère », Jacques Sakarovitch appelle « mot de Dyck » les mots bilatères et « mot de Shamir » les mots de Dyck. Les mathématiciens, en théorie combinatoire des groupes, ne connaissent que les mots bilatères et omettent l'adjectif.

Articles connexes

modifier