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 ${\displaystyle (,[,),]}$, le mot ${\displaystyle ([()[]])()}$ est bien parenthésé parce que

${\displaystyle ([()[\,]])()\to ([[\,]])()\to ([\,])()\to ()()\to ()\to \varepsilon }$.

Donnons la définition formelle d'un mot de Dyck. Soit ${\displaystyle A}$ un alphabet, et soit ${\displaystyle {\bar {A}}=\{{\bar {a}}\mid a\in A\}}$ une copie de ${\displaystyle A}$ disjointe de ${\displaystyle A}$. Sur l'ensemble ${\displaystyle (A\cup {\bar {A}})^{*}}$ des mots sur ${\displaystyle A\cup {\bar {A}}}$, on définit la relation suivante :

${\displaystyle w\to w'}$ s'il existe une factorisation ${\displaystyle w=xa{\bar {a}}y}$ telle que ${\displaystyle w'=xy}$, avec ${\displaystyle a\in A}$.

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 ${\displaystyle \varepsilon }$. Le langage de Dyck sur ${\displaystyle A\cup {\bar {A}}}$ 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 ${\displaystyle (A\cup {\bar {A}})^{*}}$.
• Un mot Dyck premier est un mot de Dyck qui n'est pas une concaténation de plusieurs mots de Dyck. On note ${\displaystyle D_{A}}$ ou ${\displaystyle D}$ l'ensemble des mots Dyck premiers, et ${\displaystyle D_{A}^{*}}$ ou ${\displaystyle D^{*}}$ le langage de Dyck. On rencontre aussi la notation ${\displaystyle D_{n}^{*}}$ lorsque l'alphabet contient ${\displaystyle n}$ lettres.
• L'ensemble des mots de Dyck premiers est un code bifixe (c'est-à-dire un code préfixe et suffixe). Les monoïdes ${\displaystyle D_{A}^{*}}$ 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 :
         ${\displaystyle {\begin{array}{rcl}S&\to &TS\mid \varepsilon \\T&\to &aS{\bar {a}}\quad (a\in A)\end{array}}}$
  La variable ${\displaystyle S}$ engendre le langage de Dyck ${\displaystyle D_{A}^{*}}$, la variable ${\displaystyle T}$ engendre le langage des mots Dyck premiers ${\displaystyle D_{A}}$.
• Une autre grammaire fréquemment rencontrée est :
         ${\displaystyle {\begin{array}{rcl}S&\to &SS\mid \varepsilon \\S&\to &aS{\bar {a}}\quad (a\in A)\end{array}}}$
  La variable ${\displaystyle S}$ engendre le langage de Dyck ${\displaystyle D_{A}^{*}}$, 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 ${\displaystyle L}$ 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:
         ${\displaystyle L=h(K\cap g^{-1}(D_{2}^{*}))}$
  où ${\displaystyle h}$ et ${\displaystyle g}$ sont des morphismes et ${\displaystyle K}$ est un langage rationnel.
• De manière équivalente, cet énoncé signifie que tout langage algébrique est image de ${\displaystyle D_{2}^{*}}$ par une transduction rationnelle, ou encore que le langage ${\displaystyle D_{2}^{*}}$ 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é TC⁰ (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 ${\displaystyle 2n}$ est égal au nombre de Catalan ${\displaystyle C_{n}}$.
• 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 ${\displaystyle a^{-1}a=1}$ dans un groupe. Ici, on utilise plutôt ${\displaystyle {\bar {a}}}$ pour symboliser l’inverse de la lettre ${\displaystyle a}$. 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 ${\displaystyle A}$ un alphabet, et soit ${\displaystyle {\bar {A}}=\{{\bar {a}}\mid a\in A\}}$ une copie de ${\displaystyle A}$ disjointe de ${\displaystyle A}$. Ici, la copie ${\displaystyle {\bar {a}}}$ de la lettre ${\displaystyle a}$ est vue comme son inverse formelle. Sur l'ensemble ${\displaystyle (A\cup {\bar {A}})^{*}}$ des mots sur ${\displaystyle A\cup {\bar {A}}}$, on définit une relation de réduction comme suit :

${\displaystyle w\to w'}$ s'il existe une factorisation ${\displaystyle w=xa{\bar {a}}y}$ ou ${\displaystyle w=x{\bar {a}}ay}$ telle que ${\displaystyle w'=xy}$, avec ${\displaystyle a\in A}$. La réduction de Dyck bilatère est la fermeture transitive de cette relation.

Par exemple, on a

${\displaystyle {\bar {a}}aa{\bar {a}}\to a{\bar {a}}\to \varepsilon }$

Un mot de Dyck bilatère est un mot qui se réduit au mot vide ${\displaystyle \varepsilon }$. 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 ${\displaystyle a{\bar {a}}}$ ou ${\displaystyle {\bar {a}}a}$) unique. L'ensemble des mots irréductibles est un langage rationnel. Il est en bijection avec le groupe libre sur ${\displaystyle A}$.

Le langage de Dyck bilatère sur ${\displaystyle A\cup {\bar {A}}}$ est l'ensemble des mots de Dyck bilatères.

Propriétés

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

${\displaystyle {\begin{array}{rcl}S&\to &TS\mid \varepsilon \\T&\to &aS{\bar {a}}\quad (a\in A)\\T&\to &{\bar {a}}Sa\quad (a\in A)\end{array}}}$

Cette grammaire est ambiguë. Par exemple, le mot ${\displaystyle a{\bar {a}}a{\bar {a}}}$ a les deux dérivations gauches suivantes :

${\displaystyle {\begin{array}{l}S\to TS\to aS{\bar {a}}S\to a{\bar {a}}S\to a{\bar {a}}TS\to a{\bar {a}}aS{\bar {a}}S\to a{\bar {a}}a{\bar {a}}S\to a{\bar {a}}a{\bar {a}}\\S\to TS\to aS{\bar {a}}S\to aTS{\bar {a}}S\to a{\bar {a}}Sa{\bar {a}}S\to a{\bar {a}}a{\bar {a}}S\to a{\bar {a}}a{\bar {a}}\end{array}}}$

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

${\displaystyle {\begin{array}{rcl}S&\to &cS_{c}{\bar {c}}S\quad (c\in A\cup {\bar {A}})\\S_{c}&\to &bS_{b}{\bar {b}}S_{c}\quad (b,c\in A\cup {\bar {A}},b\neq {\bar {c}})\\S&\to &\varepsilon \\S_{c}&\to &\varepsilon \quad (c\in A\cup {\bar {A}})\end{array}}}$

Dans le cas où l'alphabet ${\displaystyle A}$ est composé d'une seule lettre ${\displaystyle a}$, cette grammaire se réduit à :

${\displaystyle {\begin{array}{rcl}S&\to &aS_{a}{\bar {a}}S\mid {\bar {a}}S_{\bar {a}}aS\mid \varepsilon \\S_{a}&\to &aS_{a}{\bar {a}}S_{a}\mid \varepsilon \\S_{\bar {a}}&\to &{\bar {a}}S_{\bar {a}}aS_{\bar {a}}\mid \varepsilon \end{array}}}$

• 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

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Jean-Michel Autebert, Langages algébriques, Masson, 1987, 278 p. (ISBN 978-2-225-81087-9)
• (en) Wilhelm Magnus, Abraham Karrass et Donald Solitar, Combinatorial Group Theory. Presentations of groups in terms of generators and relations, Dover Publications, 2004, 444 p. (ISBN 0-486-43830-9, lire en ligne)
  Réimpression de la seconde édition, de 1976

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

• Portail des mathématiques
• Portail de l'informatique théorique