Lenguaje de Dyck

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]​ Un lenguaje de Dyck es aquel cuyas expresiones tienen los paréntesis correctamente anidados.

Valgan como ejemplo las siguientes expresiones: El lenguaje de Dyck

se define mediante la siguiente gramática formal:[2]​ O de manera abreviada: Donde

se define el lenguaje de Dyck

parejas distintas de paréntesis correctamente anidados.

, entonces la gramática del lenguaje de Dyck

es:[2]​ O de manera abreviada: Generalizando para todo