Langage de Dyck

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 formé de parenthèses ouvrantes, et de parenthèses fermantes correspondantes. Par exemple, sur la paire de parenthèses formée de '(' et ')', le mot '(())()' est bien parenthésé, et est donc un mot de Dyck, alors que le mot '())(' ne l'est pas.

Formellement, un mot est bien parenthésé 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

Les langages de Dyck jouent un rôle important en informatique théorique. Le théorème de Chomsky Schützenberger stipule en effet que tout langage algébrique est image d'un langage de Dyck.

Les langages de Dyck ont été nommés ainsi d'après le mathématicien allemand Walther von Dyck.

Définition formelle[modifier | modifier le code]

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 réduction de Dyck comme suit :

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[modifier | modifier le code]

  • Le produit 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 produit 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.
  • Un 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 stipule 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 de l'image homomorphe inverse du langage de Dyck sur deux paires de parenthèses un langage rationnel:
           L=h(g^{-1}(D_2^*)\cap K)
    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 (en) 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 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[modifier | modifier le code]

Ces langages sont reliés à la définition des groupes libres.

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 a a \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[modifier | modifier le code]

  • 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 aSa\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 aS \to a\bar a S  \to a\bar aTS  \to a\bar aaS\bar aS     \to a\bar aa\bar aS\to a\bar aa\bar a \\
S \to TS \to aS\bar aS \to aTS\bar aS \to a\bar aSa\bar aS \to a\bar aa\bar aS\to a\bar aa\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\ne \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 aS\mid \bar a S_{\bar a}aS\mid\varepsilon\\
S_a&\to&aS_a\bar aS_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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]