Lenguaje Dyck

Lenguaje que consta de cadenas equilibradas de paréntesis

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 paréntesis. El conjunto de palabras Dyck forma un lenguaje 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 corchetes correctamente anidada, como expresiones aritméticas o algebraicas.

Definición formal

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

${\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, el "]" correspondiente y un elemento del lenguaje Dyck.

Una gramática alternativa libre de contexto para el lenguaje Dyck se da en la producción:

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

Es decir, S es cero o más ocurrencias de la combinación de "[", un elemento del lenguaje Dyck, y un "]" correspondiente, donde múltiples elementos del lenguaje Dyck en el lado derecho de la producción son libres de diferir entre sí.

Definición alternativa

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

${\displaystyle \operatorname {insert} (u,j)}$está con " " insertado en la posición th ${\displaystyle u}$ ${\displaystyle []}$ ${\displaystyle j}$

${\displaystyle \operatorname {delete} (u,j)}$está con " " eliminado de la posición ${\displaystyle u}$ ${\displaystyle []}$ ${\displaystyle j}$

con el entendimiento de que no está definido para y no está definido si . Definimos una relación de equivalencia en de la siguiente manera: para elementos tenemos si y solo si existe una secuencia de cero o más aplicaciones de las funciones y que comiencen con y terminen con . El hecho de que se permita la secuencia de cero operaciones explica la reflexividad de . La simetría se desprende de la observación de que cualquier secuencia finita de aplicaciones de a una cadena se puede deshacer con una secuencia finita de aplicaciones de . La transitividad se desprende claramente de la definición. ${\displaystyle \operatorname {insert} (u,j)}$ ${\displaystyle j>|u|}$ ${\displaystyle \operatorname {delete} (u,j)}$ ${\displaystyle j>|u|-2}$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle a,b\in \Sigma ^{*}}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle \operatorname {insert} }$ ${\displaystyle \operatorname {delete} }$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle R}$ ${\displaystyle \operatorname {insert} }$ ${\displaystyle \operatorname {delete} }$

La relación de equivalencia divide el lenguaje en clases de equivalencia. Si tomamos como denotación la cadena vacía, entonces el lenguaje correspondiente a la clase de equivalencia se denomina lenguaje Dyck . ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \epsilon }$ ${\displaystyle \operatorname {Cl} (\epsilon )}$

Generalizaciones

Lenguaje Dyck tipificado

Existen variantes del lenguaje Dyck con múltiples delimitadores, por ejemplo, Dyck-2 en el alfabeto "(", ")", "[" y "]". Las palabras de este tipo de lenguaje son las que están bien separadas entre paréntesis para todos los delimitadores, es decir, se puede leer la palabra de izquierda a derecha, se pueden insertar todos los delimitadores de apertura en la pila y, siempre que lleguemos a un delimitador de cierre, debemos poder sacar el delimitador de apertura correspondiente de la parte superior de la pila. (El algoritmo de conteo anterior no se generaliza).

Por ejemplo, la siguiente es una oración válida en Dyck-3:

( [ [ ] { } ] ( ) { ( ) } ) [ ]

Profundidad finita

Una oración en lengua Dyck puede ser descrita como un descenso y un ascenso a través de los niveles de corchetes anidados. A medida que se lee una oración en lengua Dyck, cada corchete de apertura aumenta la profundidad de anidación en 1, y cada corchete de cierre disminuye en 1. La profundidad de una oración es la profundidad máxima alcanzada dentro de la oración.

Por ejemplo, podemos anotar la siguiente oración con la profundidad en cada paso:

0 ( 1 [ 2 [ 3 ] 2 { 3 } 2 ] 1 ( 2 ) 1 { 2 ( 3 ) 2 } 1 ) 0 [ 1 ] 0

y toda la oración tiene profundidad 3.

Definimos Dyck-(k, m) como el lenguaje con k tipos de corchetes y profundidad máxima m. Esto tiene aplicaciones en la teoría formal de redes neuronales recurrentes . ^[1]

Propiedades

• El lenguaje Dyck está cerrado bajo la operación de concatenación .
• Al tratarlo como un monoide algebraico bajo concatenación, vemos que la estructura del monoide se transfiere al cociente , lo que da como resultado el monoide sintáctico del lenguaje Dyck . La clase se denotará como . ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma ^{*}/R}$ ${\displaystyle \operatorname {Cl} (\epsilon )}$ ${\displaystyle 1}$
• El monoide sintáctico de la lengua Dyck no es conmutativo : si y entonces . ${\displaystyle u=\operatorname {Cl} ([)}$ ${\displaystyle v=\operatorname {Cl} (])}$ ${\displaystyle uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu}$
• Con la notación anterior, pero ni ni son invertibles en . ${\displaystyle uv=1}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \Sigma ^{*}/R}$
• El monoide sintáctico de la lengua Dyck es isomorfo al semigrupo bicíclico en virtud de las propiedades de y descritas anteriormente. ${\displaystyle \operatorname {Cl} ([)}$ ${\displaystyle \operatorname {Cl} (])}$
• 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 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 . ^[3] ${\displaystyle TC^{0}}$
• El número de palabras Dyck distintas con exactamente n pares de paréntesis y k pares más internos (es decir, la subcadena ) es el número de Narayana . ${\displaystyle [\ ]}$ ${\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 . Nótese 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 , tal como se definió en el punto anterior. Como k puede variar de 0 a n , obtenemos la siguiente igualdad, que de hecho se cumple: ${\displaystyle C_{n}}$

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

Ejemplos

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

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

Habiendo introducido las palabras de Dyck de longitud , podemos introducir una relación sobre ellas. Para cada definimos una relación sobre ; porque tenemos si y sólo si se puede llegar a desde mediante una serie de intercambios propios . Un intercambio propio en una palabra intercambia una ocurrencia de '][' con '[]'. Para cada la relación se convierte en un conjunto parcialmente ordenado . La relación es reflexiva porque una secuencia vacía de intercambios propios lleva a . La transitividad se deduce porque podemos extender una secuencia de intercambios propios que lleva a concatenándola con una secuencia de intercambios propios que lleva a formando una secuencia que lleva a . Para ver que también es antisimétrica introducimos una función auxiliar definida como una suma sobre todos los prefijos de : ${\displaystyle n}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle u,v\in {\mathcal {D}}_{n}}$ ${\displaystyle (u,v)\in S_{n}}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle u\in {\mathcal {D}}_{n}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle S_{n}}$ ${\displaystyle {\mathcal {D}}_{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle w}$ ${\displaystyle S_{n}}$ ${\displaystyle \sigma _{n}:{\mathcal {D}}_{n}\rightarrow \mathbb {N} }$ ${\displaystyle v}$ ${\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 es estrictamente monótono con respecto a los intercambios adecuados. ${\displaystyle \sigma _{n}}$

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

El conjunto parcialmente ordenado se muestra en la ilustración que acompaña a la introducción si interpretamos a [ como subiendo y ] como bajando. ${\displaystyle D_{8}}$

Véase también

• Congruencia de Dyck
• Palabra enrejada

Notas

1. Hewitt, John; Hahn, Michael; Ganguli, Surya; Liang, Percy; Manning, Christopher D. (15 de octubre de 2020). "Las RNN pueden generar lenguajes jerárquicos acotados con memoria óptima". arXiv : 2010.07515 [cs.CL].
2. Kambites, Comunicaciones en Álgebra Volumen 37 Número 1 (2009) 193-208
3. Barrington y Corbett, Cartas de procesamiento de información 32 (1989) 251-256

Referencias

• El lenguaje Dyck en PlanetMath .
• Una prueba del teorema de Chomsky-Schützenberger
• Una entrada del blog de AMS sobre las palabras de Dyck