Lenguaje de Dyck

En la teoría de los lenguajes formales de las ciencias de la computación, las matemáticas y la lingüística, un lenguaje de Dyck es un lenguaje libre de contexto que está formado por palabras balanceadas de paréntesis. Es importante para el análisis sintáctico de expresiones que deben tener una secuencia de paréntesis correctamente anidados, como las expresiones aritméticas y algebraicas. Toma su nombre del matemático alemán Walther von Dyck, que estudió en profundidad la teoría de grupos.

Los lenguajes de Dyck son cruciales en la teoría de los lenguajes formales ya que, según el teorema de Chomsky-Schützenberger, cualquier lenguaje libre de contexto se puede expresar como el homomorfismo de la intersección de un lenguaje regular y un lenguaje de Dyck.^[1]​^[2]​^[3]​

Definición formal

Concepto

Un lenguaje de Dyck es aquel cuyas expresiones tienen los paréntesis correctamente anidados. Valgan como ejemplo las siguientes expresiones:

• La expresión ${\displaystyle [[()[]]()]}$ sí pertenece a los lenguajes de Dyck
• La expresión ${\displaystyle ([)]}$ no pertenece a un lenguaje de Dyck
• La expresión ${\displaystyle ))}$ no pertenece a un lenguaje de Dyck

Definición

El lenguaje de Dyck ${\displaystyle D}$ se define mediante la siguiente gramática formal:^[2]​

${\displaystyle S\rightarrow \varepsilon }$

${\displaystyle S\rightarrow SS}$

${\displaystyle S\rightarrow (S)}$

O de manera abreviada:

${\displaystyle S\to SS~|~(S)~|~\varepsilon }$

Donde ${\displaystyle \varepsilon }$ es la cadena vacía y ${\displaystyle S}$ es un símbolo no terminal.

Generalización

Para cada número natural ${\displaystyle n\in \mathbb {N} }$ se define el lenguaje de Dyck ${\displaystyle D_{n}}$ como aquel que tiene ${\displaystyle n}$ parejas distintas de paréntesis correctamente anidados.

De este modo, si el lenguaje de Dyck ${\displaystyle D_{2}}$ tiene las dos parejas ${\displaystyle (~)}$ y ${\displaystyle [~]}$, entonces la gramática del lenguaje de Dyck ${\displaystyle D_{2}}$ es:^[2]​

${\displaystyle S\to \varepsilon }$

${\displaystyle S\to SS}$

${\displaystyle S\to (S)}$

${\displaystyle S\to [S]}$

O de manera abreviada:

${\displaystyle S\to SS~|~(S)~|~[S]~|~\varepsilon }$

Generalizando para todo ${\displaystyle n\in \mathbb {N} }$, para cada ${\displaystyle D_{n}}$ existen las correspondientes ${\displaystyle n}$ producciones del tipo ${\displaystyle S\to \{S\}}$.

Propiedades

• El número de posibles expresiones (palabras) de longitud ${\displaystyle 2j}$ en el lenguaje de Dyck ${\displaystyle D_{1}}$ viene dado por ${\displaystyle C_{j}}$, donde ${\displaystyle C_{j}}$ es el número de Catalan. Los llamados 'caminos de Dyck' son una representación gráfica de esta propiedad.^[4]​

Véase también

• Número de Catalan
• Teorema de Chomsky-Schützenberger
• Gramática libre de contexto
• Lenguaje formal
• Walther von Dyck

Referencias