Lenguaje de Dyck

En la teoría de los lenguajes formales de la informática , las matemáticas y la lingüística , una palabra de Dyck es una cadena equilibrada de paréntesis. El conjunto de palabras de Dyck forma un lenguaje de Dyck . El más simple, Dyck-1, utiliza solo dos paréntesis coincidentes, por ejemplo ( y ).

Las palabras y el lenguaje de Dyck reciben su nombre del matemático Walther von Dyck . Tienen aplicaciones en el análisis sintáctico de expresiones que deben tener una secuencia de paréntesis anidada correctamente, como expresiones aritméticas o algebraicas.

Dejar${\displaystyle \Sigma =\{[,]\}}$Sea el alfabeto formado por los símbolos [ y ].${\displaystyle \Sigma ^{*}}$denotamos su clausura de Kleene . El lenguaje de Dyck se define como:

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ todos los prefijos de }}u{\text{ no contienen más ] que ['s}}{\text{ y el número de ['s en }}u{\text{ es igual al número de ]'s}}\}.}$

• El lenguaje Dyck es cerrado bajo la operación de concatenación .
• Al tratar${\displaystyle \Sigma ^{*}}$como un monoide algebraico bajo concatenación vemos que la estructura del monoide se transfiere al cociente${\displaystyle \Sigma ^{*}/R}$, lo que da como resultado el monoide sintáctico del lenguaje de Dyck . La clase${\displaystyle \operatorname {Cl} (\epsilon )}$se denotará${\displaystyle 1}$.
• El monoide sintáctico del lenguaje de Dyck no es conmutativo : si${\displaystyle u=\operatorname {Cl} ([)}$y${\displaystyle v=\operatorname {Cl} (])}$entonces${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$.
• Con la notación anterior,${\displaystyle uv=1}$pero ninguno${\displaystyle u}$ni${\displaystyle v}$son invertibles en${\displaystyle \Sigma ^{*}/R}$.
• El monoide sintáctico del lenguaje de Dyck es isomorfo al semigrupo bicíclico en virtud de las propiedades de${\displaystyle \operatorname {Cl} ([)}$y${\displaystyle \operatorname {Cl} (])}$descrito anteriormente.
• Según el teorema de representación de Chomsky-Schützenberger , cualquier lenguaje libre de contexto es una imagen homomórfica de la intersección de algún lenguaje regular con un lenguaje de Dyck en uno o más tipos de pares de corchetes. ^{[ 2 ]}
• El lenguaje Dyck con dos tipos distintos de corchetes se puede reconocer en la clase de complejidad.${\displaystyle TC^{0}}$. ^{[ 3 ]}
• El número de palabras de Dyck distintas con exactamente n pares de paréntesis y k pares internos (es decir, la subcadena${\displaystyle [\ ]}$) es el número de Narayana${\displaystyle \operatorname {N} (n,k)}$.
• Las palabras de Dyck son isomorfas a los caminos de Dyck , un subconjunto de los símbolos de recorrido en escalera.
• El número de palabras de Dyck distintas con exactamente n pares de paréntesis es el n -ésimo número de Catalan.${\displaystyle C_{n}}$Nótese que el lenguaje de Dyck de palabras con n pares de paréntesis es igual a la unión, sobre todos los posibles k , de los lenguajes de Dyck de palabras con n pares de paréntesis y k pares internos , tal como se definió en el punto anterior. Dado que k puede variar de 0 a n , obtenemos la siguiente igualdad, que efectivamente se cumple:

${\displaystyle C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)}$

Podemos definir una relación de equivalencia.${\displaystyle L}$sobre el lenguaje de Dyck${\displaystyle {\mathcal {D}}}$. Para${\displaystyle u,v\in {\mathcal {D}}}$tenemos${\displaystyle (u,v)\in L}$si y solo si${\displaystyle |u|=|v|}$, es decir${\displaystyle u}$y${\displaystyle v}$tienen la misma longitud. Esta relación particiona el lenguaje de Dyck:${\displaystyle {\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal {D}}_{1},\ldots \}}$. Tenemos${\displaystyle {\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D}}_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}}$dónde${\displaystyle {\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}}$. Tenga en cuenta que${\displaystyle {\mathcal {D}}_{n}}$está vacío para impar${\displaystyle n}$.

Habiendo introducido las palabras de Dyck de longitud${\displaystyle n}$, podemos introducir una relación sobre ellos. Para cada${\displaystyle n\in \mathbb {N} }$definimos una relación${\displaystyle S_{n}}$en${\displaystyle {\mathcal {D}}_{n}}$; para${\displaystyle u,v\in {\mathcal {D}}_{n}}$tenemos${\displaystyle (u,v)\in S_{n}}$si y solo si${\displaystyle v}$Se puede acceder desde${\displaystyle u}$mediante una serie de intercambios adecuados . Un intercambio adecuado en una palabra${\displaystyle u\in {\mathcal {D}}_{n}}$intercambia una ocurrencia de '][' con '[]'. Para cada${\displaystyle n\in \mathbb {N} }$la relación${\displaystyle S_{n}}$marcas${\displaystyle {\mathcal {D}}_{n}}$en un conjunto parcialmente ordenado . La relación${\displaystyle S_{n}}$es reflexivo porque una secuencia vacía de intercambios adecuados toma${\displaystyle u}$a${\displaystyle u}$La transitividad se deduce porque podemos extender una secuencia de intercambios propios que toma${\displaystyle u}$a${\displaystyle v}$al concatenarlo con una secuencia de intercambios adecuados que toma${\displaystyle v}$a${\displaystyle w}$formando una secuencia que toma${\displaystyle u}$en${\displaystyle w}$Para ver eso${\displaystyle S_{n}}$También es antisimétrico, introducimos una función auxiliar.${\displaystyle \sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N} }$definido como una suma sobre todos los prefijos${\displaystyle v}$de${\displaystyle u}$:

${\displaystyle \sigma _{n}(u)=\sum _{vw=u}{\Big (}({\text{count of ['s in }}v)-({\text{count of ]'s in }}v){\Big )}}$

La siguiente tabla ilustra que${\displaystyle \sigma _{n}}$es estrictamente monótono con respecto a los intercambios adecuados.

Por eso${\displaystyle \sigma _{n}(u')-\sigma _{n}(u)=2>0}$entonces${\displaystyle \sigma _{n}(u)<\sigma _{n}(u')}$cuando hay un intercambio adecuado que toma${\displaystyle u}$en${\displaystyle u'}$Ahora bien, si asumimos que ambos${\displaystyle (u,v),(v,u)\in S_{n}}$y${\displaystyle u\neq v}$, entonces existen secuencias no vacías de intercambios propios tales${\displaystyle u}$es llevado a${\displaystyle v}$y viceversa. Pero entonces${\displaystyle \sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)}$lo cual no tiene sentido. Por lo tanto, siempre que ambos${\displaystyle (u,v)}$y${\displaystyle (v,u)}$están en${\displaystyle S_{n}}$, tenemos${\displaystyle u=v}$, por eso${\displaystyle S_{n}}$es antisimétrico.

El conjunto ordenado parcial${\displaystyle D_{8}}$se muestra en la ilustración que acompaña a la introducción si interpretamos un [ como hacia arriba y ] como hacia abajo.

• Congruencia de Dyck
• Palabra reticular

• Lenguaje Dyck en PlanetMath .
• Una demostración del teorema de Chomsky-Schützenberger
• Una entrada del blog de AMS sobre las palabras de Dyck