Langage de Dyck

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 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.

Sommaire

Définition formelle

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 ε. 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

  • 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 DA 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 DA.

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

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 (en) des langages algébriques.
  • Le langage de Dyck sur deux paires de parenthèses appartient à la classe de complexité nombre de Catalan Cn.
  • Le monoïde syntaxique du langage de Dyck est le monoïde bicyclique (en).

Langages de Dyck bilatères

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 aytelle 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 ε. Lz 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 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.

Voir aussi

Références

  • Wilhelm Magnus, Abraham Karrass et Donald Solitar, Combinatorial Group Theory. Presentations of groups in terms of generators and relations, Dover Publications, 2004 (ISBN 0-486-43830-9).
    Réimpression de la seconde édition, de 1976
     

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Langage de Dyck de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Langage algébrique — En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les… …   Wikipédia en Français

  • Langage rationnel — Les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes: ce sont les langages décrits par les expressions régulières ou rationnelles,d où le nom de langages réguliers; …   Wikipédia en Français

  • Walther von Dyck — Walther Franz Anton von Dyck[1], né le 6 décembre 1856 à Munich et mort le 5 novembre 1934 à Munich, est un mathématicien allemand. Il est considéré comme le premier[réf. souhaitée] à avoir donné la définition moderne des …   Wikipédia en Français

  • Walther Franz Anton von Dyck — Walther von Dyck Walther Franz Anton von Dyck, né le 6 décembre 1856 à Munich et mort le 5 novembre 1934 à Munich, est un mathématicien allemand. Il est considéré comme le premier à avoir défini un groupe, dans le sens moderne du terme. Il… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Grammaire linéaire — En informatique théorique, et notamment en théorie des langages, on appelle grammaire linéaire une grammaire algébrique dont tous les membres droits de règles contiennent au plus un symbole non terminal. Un langage linéaire est un langage qui est …   Wikipédia en Français

  • Nombre de Catalan — En mathématiques combinatoires, les nombres de Catalan forment une suite de nombres naturels utilisée dans divers problèmes de dénombrement , impliquant souvent de façon récursive des objets définis. Ils sont nommés ainsi d après le mathématicien …   Wikipédia en Français

  • Marcel-Paul Schützenberger — Pour les articles homonymes, voir Schutzenberger. Marcel Paul Schützenberger (né le 24 octobre 1920 à Paris, mort le 29 juillet 1996 à Paris) est un scientifique français. Ses recherches ont d abord porté sur la médecine et la biologie, mais il… …   Wikipédia en Français

  • Transduction rationnelle — En informatique théorique, en linguistique, en théorie des automates et en théorie des langages, une transduction rationnelle est une transformation de mots et de langages définie par un transducteur fini ou au moyen d une relation rationnelle.… …   Wikipédia en Français

  • Hiérarchie de Chomsky — En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky est une classification des langages formels et des grammaires formelles, décrite par Noam Chomsky en 1956[1]. Cette section ne cite pas suffisamment …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”