Lenguaje de Dyck

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

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[editar]

Concepto[editar]

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

  • La expresión pertenece a los lenguajes de Dyck
  • La expresión no pertenece a un lenguaje de Dyck
  • La expresión no pertenece a un lenguaje de Dyck
Caminos de Dyck. Diagrama de las 14 posibles palabras de Dyck de longitud 8. ( y ) están representados como arriba y abajo

Definición[editar]

El lenguaje de Dyck se define mediante la siguiente gramática formal:[2]

O de manera abreviada:

Donde es la cadena vacía y es un símbolo no terminal.

Generalización[editar]

Para cada número natural se define el lenguaje de Dyck como aquel que tiene parejas distintas de paréntesis correctamente anidados.

De este modo, si el lenguaje de Dyck tiene las dos parejas y , entonces la gramática del lenguaje de Dyck es:[2]

O de manera abreviada:

Generalizando para todo , para cada existen las correspondientes producciones del tipo .

Propiedades[editar]

  • El número de posibles expresiones (palabras) de longitud en el lenguaje de Dyck viene dado por , donde 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[editar]

Referencias[editar]

  1. Kanazawa, Makoto; Kracht, Markus; Seki, Hiroyuki; Kornai, András (2011). The mathematics of language. Nara, Japan: Springer. p. 42. ISBN 9783642232107. Consultado el 10 de abril de 2015. 
  2. a b c Simon, Matthew (1999). Automata Theory. World Scientific. p. 198. ISBN 9789810237530. Consultado el 10 de abril de 2015. 
  3. Gelbukh, Alexander (2003). Computational linguistics and intelligent text processing. México, D. F.: Springer. p. 27. ISBN 9783540005322. Consultado el 10 de abril de 2015. 
  4. «Caminos de Dyck (Dyck Paths)» (en inglés). Consultado el 10 de abril de 2015.