Lenguaje Dyck

Lenguaje que consta de cadenas equilibradas de corchetes

Celosía de las 14 palabras de Dyck de longitud 8 - [ y ] interpretadas como arriba y abajo

En la teoría de los lenguajes formales de la informática , las matemáticas y la lingüística , una palabra Dyck es una cadena equilibrada de corchetes [y]. El conjunto de palabras de Dyck forma el lenguaje Dyck .

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

Definición formal

Dejar ${\displaystyle \Sigma =\{[,]\}}$ser el alfabeto que consta de los símbolos [y]. Dejar${\displaystyle \Sigma ^{*}}$denotar su cierre Kleene . El lenguaje Dyck se define como:

${\displaystyle \{u\in \Sigma ^{*}\vert {\text{ all prefixes of }}u{\text{ contain no more ]'s than ['s}}{\text{ and the number of ['s in }}u{\text{ equals the number of ]'s}}\}.}$

Gramática libre de contexto

Puede resultar útil definir el lenguaje Dyck mediante una gramática libre de contexto en algunas situaciones. El lenguaje Dyck se genera mediante la gramática libre de contexto con una única S no terminal , y la producción:

S → ε | "[" S "]" S

Es decir, S es la cadena vacía ( ε ) o es "[", un elemento del lenguaje Dyck, la coincidencia "]" y un elemento del lenguaje Dyck.

La producción proporciona una gramática alternativa libre de contexto para el lenguaje Dyck:

S → ("[" S "]") ^*

Es decir, S es cero o más ocurrencias de la combinación de "[", un elemento del lenguaje Dyck, y una coincidencia "]", donde varios elementos del lenguaje Dyck en el lado derecho de la producción pueden diferir libremente de mutuamente.

Definición alternativa

En otros contextos, en cambio, puede ser útil definir el lenguaje Dyck dividiendo ${\displaystyle \Sigma ^{*}}$en clases de equivalencia, como sigue. Para cualquier elemento${\displaystyle u\in \Sigma ^{*}}$ de longitud ${\displaystyle |u|}$, definimos funciones parciales ${\displaystyle \operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$ y ${\displaystyle \operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}}$ por

${\displaystyle \operatorname {insert} (u,j)}$ es ${\displaystyle u}$ con "${\displaystyle []}$"insertado en el ${\displaystyle j}$a posición

${\displaystyle \operatorname {delete} (u,j)}$ es ${\displaystyle u}$ con "${\displaystyle []}$"eliminado del ${\displaystyle j}$a posición

con el entendimiento de que ${\displaystyle \operatorname {insert} (u,j)}$ no está definido para ${\displaystyle j>|u|}$ y ${\displaystyle \operatorname {delete} (u,j)}$ no está definido si ${\displaystyle j>|u|-2}$. Definimos una relación de equivalencia ${\displaystyle R}$ en ${\displaystyle \Sigma ^{*}}$ de la siguiente manera: para elementos ${\displaystyle a,b\in \Sigma ^{*}}$ tenemos ${\displaystyle (a,b)\in R}$ si y solo si existe una secuencia de cero o más aplicaciones del ${\displaystyle \operatorname {insert} }$ y ${\displaystyle \operatorname {delete} }$ funciones que comienzan con ${\displaystyle a}$ y terminando con ${\displaystyle b}$. Que la secuencia de operaciones cero esté permitida explica la reflexividad de${\displaystyle R}$. La simetría se deriva de la observación de que cualquier secuencia finita de aplicaciones de${\displaystyle \operatorname {insert} }$ a una cuerda se puede deshacer con una secuencia finita de aplicaciones de ${\displaystyle \operatorname {delete} }$. La transitividad queda clara en la definición.

La relación de equivalencia divide el idioma ${\displaystyle \Sigma ^{*}}$en clases de equivalencia. Si tomamos${\displaystyle \epsilon }$ para denotar la cadena vacía, luego el idioma correspondiente a la clase de equivalencia ${\displaystyle \operatorname {Cl} (\epsilon )}$se llama el idioma Dyck .

Propiedades

• El lenguaje Dyck se cierra 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}$, resultando en el monoide sintáctico del lenguaje Dyck . La clase${\displaystyle \operatorname {Cl} (\epsilon )}$ será denotado ${\displaystyle 1}$.
• El monoide sintáctico del lenguaje Dyck no es conmutativo : si${\displaystyle u=\operatorname {Cl} ([)}$ y ${\displaystyle v=\operatorname {Cl} (])}$ luego ${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$.
• Con la notación de arriba, ${\displaystyle uv=1}$ pero tampoco ${\displaystyle u}$ ni ${\displaystyle v}$ son invertibles en ${\displaystyle \Sigma ^{*}/R}$.
• El monoide sintáctico del lenguaje Dyck es isomorfo al semigrupo bicíclico en virtud de las propiedades de${\displaystyle \operatorname {Cl} ([)}$ y ${\displaystyle \operatorname {Cl} (])}$ descrito arriba.
• 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 paréntesis. ^[1]
• El lenguaje Dyck con dos tipos distintos de corchetes se puede reconocer en la clase de complejidad ${\displaystyle TC^{0}}$. ^[2]
• El número de palabras Dyck distintas con exactamente n pares de paréntesis y k pares más internos (es decir, la subcadena${\displaystyle [\ ]}$) es el número de Narayana ${\displaystyle \operatorname {N} (n,k)}$.
• El número de palabras Dyck distintas con exactamente n pares de paréntesis es el n -ésimo número catalán ${\displaystyle C_{n}}$. Observe que el lenguaje Dyck de palabras con n pares de paréntesis es igual a la unión, sobre todos los k posibles , de los lenguajes Dyck de palabras de n pares de paréntesis con k pares más internos , como se define en el punto anterior. Dado que k puede oscilar entre 0 an , obtenemos la siguiente igualdad, que de hecho se cumple:

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

Ejemplos

Podemos definir una relación de equivalencia ${\displaystyle L}$ en el idioma 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 divide el lenguaje 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}}$ donde ${\displaystyle {\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}}$. Tenga en cuenta que${\displaystyle {\mathcal {D}}_{n}}$ está vacío por extraño ${\displaystyle n}$.

Habiendo introducido las palabras largas de Dyck ${\displaystyle n}$, podemos presentarles una relación. Para cada${\displaystyle n\in \mathbb {N} }$ definimos una relación ${\displaystyle S_{n}}$ en ${\displaystyle {\mathcal {D}}_{n}}$; por${\displaystyle u,v\in {\mathcal {D}}_{n}}$ tenemos ${\displaystyle (u,v)\in S_{n}}$ si y solo si ${\displaystyle v}$ se puede llegar desde ${\displaystyle u}$mediante una serie de intercambios adecuados . Un intercambio adecuado en una palabra${\displaystyle u\in {\mathcal {D}}_{n}}$intercambia una aparición de '] [' con '[]'. Para cada${\displaystyle n\in \mathbb {N} }$ la relación ${\displaystyle S_{n}}$ hace ${\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}$ para ${\displaystyle u}$. La transitividad sigue porque podemos extender una secuencia de intercambios adecuados que toma${\displaystyle u}$ para ${\displaystyle v}$ al concatenarlo con una secuencia de intercambios adecuados que toma ${\displaystyle v}$ para ${\displaystyle w}$ formando una secuencia que lleva ${\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 de 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.

Estricta monotonicidad de ${\displaystyle \sigma _{n}}$

sumas parciales de ${\displaystyle \sigma _{n}(u)}$	${\displaystyle P}$	${\displaystyle P-1}$	${\displaystyle P}$	${\displaystyle Q}$
${\displaystyle u}$	${\displaystyle \ldots }$	]	[	${\displaystyle \ldots }$
${\displaystyle u'}$	${\displaystyle \ldots }$	[	]	${\displaystyle \ldots }$
sumas parciales de ${\displaystyle \sigma _{n}(u')}$	${\displaystyle P}$	${\displaystyle P+1}$	${\displaystyle P}$	${\displaystyle Q}$
Diferencia de sumas parciales	0	2	0	0

Por eso ${\displaystyle \sigma _{n}(u')-\sigma _{n}(u)=2>0}$ asi que ${\displaystyle \sigma _{n}(u)<\sigma _{n}(u')}$ cuando hay un intercambio adecuado que lleva ${\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 hay secuencias no vacías de intercambios adecuados como ${\displaystyle u}$ es tomado en ${\displaystyle v}$y viceversa. Pero entonces${\displaystyle \sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u)}$lo cual es absurdo. Por lo tanto, siempre que ambos${\displaystyle (u,v)}$ y ${\displaystyle (v,u)}$ estan 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 a [como subir y] como bajar.

Generalizaciones

Existen variantes del lenguaje Dyck con múltiples delimitadores, por ejemplo, en el alfabeto "(", ")", "[" y "]". Las palabras de dicho lenguaje son las que están bien entre paréntesis para todos los delimitadores, es decir, uno puede leer la palabra de izquierda a derecha, presionar cada delimitador de apertura en la pila, y siempre que alcancemos un delimitador de cierre, entonces debemos poder para sacar el delimitador de apertura correspondiente de la parte superior de la pila.

Ver también

• Congruencia Dyck
• Palabra de celosía

Notas

1. Kambites, Comunicaciones en álgebra volumen 37 número 1 (2009) 193-208
2. Barrington y Corbett, Cartas de procesamiento de información 32 (1989) 251-256

Referencias

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