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

([()[\,]])()\to ([[\,]])()\to ([\,])()\to ()()\to ()\to \varepsilon

.

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

w\to w'

s'il existe une factorisation

w=xa{\bar {a}}y

telle que

w'=xy

, avec

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

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

Par exemple, on a

{\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 $\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 $a{\bar {a}}$ ou ${\bar {a}}a$ ) unique. L'ensemble des mots irréductibles est un langage rationnel. Il est en bijection avec le groupe libre sur $A$ .

Le langage de Dyck bilatère sur $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 :

{\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 $a{\bar {a}}a{\bar {a}}$ a les deux dérivations gauches suivantes :

{\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 :

{\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 $A$ est composé d'une seule lettre $a$ , cette grammaire se réduit à :

{\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

↑ 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, n^o 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

[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, n^o 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.

[1]