Lenguaje Dyck

En la informática teórica , especialmente en la teoría del lenguaje , los lenguajes Dyck son lenguajes formales individuales. Un idioma Dyck es el conjunto de palabras bien entre paréntesis , sobre un alfabeto finito de paréntesis de apertura y cierre. Por ejemplo, en el par de paréntesis formado por ' (' y ' )' , la palabra ' (()) ()' es una palabra bien entre paréntesis, mientras que la palabra ' ()) (' no lo es.

Los lenguajes Dyck juegan un papel importante en la informática teórica para caracterizar los lenguajes algebraicos . El teorema de Schützenberger Chomsky establece en efecto que cualquier lenguaje algebraico es la imagen con un morfismo alfabético de intersección de un lenguaje Dyck con un lenguaje racional .

Los idiomas de Dyck recibieron su nombre del matemático alemán Walther von Dyck .

Definicion formal

Intuitivamente, una palabra está bien entre paréntesis , también llamada palabra de Dyck , si se puede reducir a la palabra vacía eliminando sucesivamente pares adyacentes de paréntesis del mismo tipo. Por ejemplo, en el alfabeto formado por , la palabra está entre paréntesis porque (,[,),]{\ Displaystyle (, [,),]}([()[]])(){\ Displaystyle ([() []]) ()}

([()[]])()→([[]])()→([])()→()()→()→ε{\ Displaystyle ([() [\,]]) () \ a ([[\,]]) () \ a ([\,]) () \ a () () \ a () \ a \ varepsilon}.

Démosle la definición formal de una palabra Dyck. O un alfabeto o una copia desarticulada de . Sobre el conjunto de palabras en , definimos la siguiente relación: PARA{\ Displaystyle A}PARA¯={Para¯∣Para∈PARA}{\ Displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ in A \}}PARA{\ Displaystyle A}PARA{\ Displaystyle A}(PARA∪PARA¯)∗{\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}PARA∪PARA¯{\ Displaystyle A \ cup {\ bar {A}}}

w→w′{\ Displaystyle w \ to w '}si existe una factorización como , con .w=XParaPara¯y{\ Displaystyle w = xa {\ bar {a}} y}w′=Xy{\ Displaystyle w '= xy}Para∈PARA{\ Displaystyle a \ in A}

La reducción Dyck es el cierre transitivo de esta relación. Una palabra de Dyck es una palabra que se reduce a la palabra vacía . El lenguaje Dyck en el conjunto de palabras Dyck. ε{\ Displaystyle \ varepsilon}PARA∪PARA¯{\ Displaystyle A \ cup {\ bar {A}}}

La reducción de Dyck es un sistema de reescritura confluente . La congruencia de Dyck es el cierre reflexivo, simétrico y transitivo de la relación.

Propiedades

• La concatenación de dos palabras de Dyck sigue siendo una palabra de Dyck, por lo que el lenguaje de Dyck es un submonoide del monoide libre .(PARA∪PARA¯)∗{\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}
• Una palabra principal de Dyck es una palabra de Dyck que no es una concatenación de varias palabras de Dyck. Denotamos o el conjunto de palabras Dyck primos, y o el lenguaje de Dyck. También nos encontramos con la notación cuando el alfabeto contiene letras.DPARA{\ Displaystyle D_ {A}}D{\ Displaystyle D}DPARA∗{\ Displaystyle D_ {A} ^ {*}}D∗{\ Displaystyle D ^ {*}}Dno∗{\ Displaystyle D_ {n} ^ {*}}no{\ Displaystyle n}
• El conjunto de palabras principales de Dyck es un código bifijo (es decir, un código de prefijo y sufijo). Por tanto, los monoides son submonoides libres .DPARA∗{\ Displaystyle D_ {A} ^ {*}}
• Los lenguajes Dyck y los principales lenguajes Dyck son lenguajes algebraicos deterministas. Aquí hay una gramática: la variable genera el idioma de Dyck , la variable genera el idioma de las primeras palabras de Dyck .
         S→TS∣εT→ParaSPara¯(Para∈PARA){\ Displaystyle {\ begin {array} {rcl} S & \ to & TS \ mid \ varepsilon \\ T & \ to & aS {\ bar {a}} \ quad (a \ in A) \ end {array} }}
  S{\ Displaystyle S}DPARA∗{\ Displaystyle D_ {A} ^ {*}}T{\ Displaystyle T}DPARA{\ Displaystyle D_ {A}}
• Otra gramática que se encuentra con frecuencia es: la variable genera el lenguaje de Dyck , pero la gramática es ambigua .
         S→SS∣εS→ParaSPara¯(Para∈PARA){\ Displaystyle {\ begin {array} {rcl} S & \ to & SS \ mid \ varepsilon \\ S & \ to & aS {\ bar {a}} \ quad (a \ in A) \ end {array} }}
  S{\ Displaystyle S}DPARA∗{\ Displaystyle D_ {A} ^ {*}}
• El teorema de Chomsky-Schützenberger establece que cualquier lenguaje algebraico es una imagen homomórfica de la intersección de un lenguaje Dyck con un lenguaje racional.
• Este teorema se puede refinar de la siguiente manera: cualquier lenguaje algebraico es una imagen homomórfica de la intersección de un lenguaje racional y la imagen homomórfica inversa del lenguaje de Dyck en dos pares de paréntesis: donde y son morfismos y es un lenguaje racional.LA{\ Displaystyle L}
         LA=h(K∩gramo-1(D2∗)){\ Displaystyle L = h (K \ cap g ^ {- 1} (D_ {2} ^ {*}))}
  h{\ Displaystyle h}gramo{\ Displaystyle g}K{\ Displaystyle K}
• De manera equivalente, esta afirmación significa que cualquier lenguaje algebraico es una imagen a través de la transducción racional , o que el lenguaje es un generador del cono racional de los lenguajes algebraicos.D2∗{\ Displaystyle D_ {2} ^ {*}}D2∗{\ Displaystyle D_ {2} ^ {*}}
• El lenguaje de Dyck en dos pares de paréntesis pertenece a la clase de complejidad TC 0  (en) .
• Las palabras de Dyck tienen muchas caracterizaciones y propiedades combinatorias. El número de palabras Dyck en un par de paréntesis de longitud es igual al número catalán .2no{\ Displaystyle 2n} VSno{\ Displaystyle C_ {n}}
• El monoide sintáctico del lenguaje de Dyck es el monoide bicíclico .

Idiomas bilaterales de Dyck

Intuitivamente, una palabra Dyck de dos caras es una palabra bien formada de símbolos y sus inversas que se simplifican cuando son adyacentes, como en un grupo. Aquí, se usa en cambio para simbolizar el reverso de la letra . Los lenguajes Dyck de dos caras, formados por palabras Dyck de dos caras, están relacionados con la definición de grupos libres . Para-1Para=1{\ Displaystyle a ^ {- 1} a = 1}Para¯{\ displaystyle {\ bar {a}}}Para{\ Displaystyle a}

O un alfabeto o una copia desarticulada de . Aquí, la copia de la carta se ve como su reverso formal. En el conjunto de palabras en , definimos una relación de reducción de la siguiente manera: PARA{\ Displaystyle A}PARA¯={Para¯∣Para∈PARA}{\ Displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ in A \}}PARA{\ Displaystyle A}PARA{\ Displaystyle A}Para¯{\ displaystyle {\ bar {a}}}Para{\ Displaystyle a}(PARA∪PARA¯)∗{\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}PARA∪PARA¯{\ Displaystyle A \ cup {\ bar {A}}}

w→w′{\ Displaystyle w \ to w '}si hay factorización o tal que , con . La reducción de Dyck bilateral es el cierre transitivo de esta relación. w=XParaPara¯y{\ Displaystyle w = xa {\ bar {a}} y}w=XPara¯Paray{\ Displaystyle w = x {\ bar {a}} ay}w′=Xy{\ Displaystyle w '= xy}Para∈PARA{\ Displaystyle a \ in A}

Por ejemplo, tenemos

Para¯ParaParaPara¯→ParaPara¯→ε{\ Displaystyle {\ bar {a}} aa {\ bar {a}} \ to a {\ bar {a}} \ to \ varepsilon}

Una palabra Dyck de dos caras es una palabra que se reduce a la palabra vacía . La relación de reescritura definida anteriormente es confluente, y cualquier palabra se reduce a una palabra irreductible (es decir, que no contiene ningún factor o un factor único ) . El conjunto de palabras irreductibles es un lenguaje racional . Está en inyección con el grupo libre . ε{\ Displaystyle \ varepsilon}ParaPara¯{\ Displaystyle a {\ bar {a}}}Para¯Para{\ displaystyle {\ bar {a}} a}PARA{\ Displaystyle A}

El lenguaje Dyck de dos caras en el conjunto de palabras de Dyck de dos caras. PARA∪PARA¯{\ Displaystyle A \ cup {\ bar {A}}}

Propiedades

• Los lenguajes Dyck bilaterales son algebraicos. Aquí hay una gramática:

S→TS∣εT→ParaSPara¯(Para∈PARA)T→Para¯SPara(Para∈PARA){\ Displaystyle {\ begin {array} {rcl} S & \ to & TS \ mid \ varepsilon \\ T & \ to & aS {\ bar {a}} \ quad (a \ in A) \\ T & \ a & {\ bar {a}} Sa \ quad (a \ in A) \ end {array}}}

Esta gramática es ambigua. Por ejemplo, la palabra tiene las siguientes dos derivaciones a la izquierda : ParaPara¯ParaPara¯{\ Displaystyle a {\ bar {a}} a {\ bar {a}}}

S→TS→ParaSPara¯S→ParaPara¯S→ParaPara¯TS→ParaPara¯ParaSPara¯S→ParaPara¯ParaPara¯S→ParaPara¯ParaPara¯S→TS→ParaSPara¯S→ParaTSPara¯S→ParaPara¯SParaPara¯S→ParaPara¯ParaPara¯S→ParaPara¯ParaPara¯{\ Displaystyle {\ begin {array} {l} S \ to TS \ to aS {\ bar {a}} S \ to a {\ bar {a}} S \ to a {\ bar {a}} TS \ a {\ bar {a}} aS {\ bar {a}} S \ a {\ bar {a}} a {\ bar {a}} S \ a {\ bar {a}} a {\ bar {a}} \\ S \ to TS \ to aS {\ bar {a}} S \ to aTS {\ bar {a}} S \ to a {\ bar {a}} Sa {\ bar {a} } S \ a {\ bar {a}} a {\ bar {a}} S \ a {\ bar {a}} a {\ bar {a}} \ end {array}}}

Hay gramáticas inequívocas para los lenguajes Dyck de dos caras. Acá hay uno:

S→vsSvsvs¯S(vs∈PARA∪PARA¯)Svs→BSBB¯Svs(B,vs∈PARA∪PARA¯,B≠vs¯)S→εSvs→ε(vs∈PARA∪PARA¯){\ Displaystyle {\ begin {array} {rcl} S & \ to & cS_ {c} {\ bar {c}} S \ quad (c \ in A \ cup {\ bar {A}}) \\ S_ { c} & \ to & bS_ {b} {\ bar {b}} S_ {c} \ quad (b, c \ in A \ cup {\ bar {A}}, b \ neq {\ bar {c}} ) \\ S & \ to & \ varepsilon \\ S_ {c} & \ to & \ varepsilon \ quad (c \ in A \ cup {\ bar {A}}) \ end {array}}}

En el caso de que el alfabeto esté compuesto por una sola letra , esta gramática se reduce a: PARA{\ Displaystyle A}Para{\ Displaystyle a}

S→ParaSParaPara¯S∣Para¯SPara¯ParaS∣εSPara→ParaSParaPara¯SPara∣εSPara¯→Para¯SPara¯ParaSPara¯∣ε{\ Displaystyle {\ begin {array} {rcl} S & \ to & aS_ {a} {\ bar {a}} S \ mid {\ bar {a}} S _ {\ bar {a}} aS \ mid \ varepsilon \ \ S_ {a} & \ to & aS_ {a} {\ bar {a}} S_ {a} \ mid \ varepsilon \\ S _ {\ bar {a}} & \ to & {\ bar { a}} S_ {\ bar {a}} aS _ {\ bar {a}} \ mid \ varepsilon \ end {array}}}

• El teorema de Chomsky-Schützenberger sigue siendo válido cuando los lenguajes Dyck son reemplazados por lenguajes Dyck bilaterales.

Referencias

• Olivier Carton , lenguajes formales, computabilidad y complejidad ,2008[ detalle de la edición ] ( leer en línea )
• Jean-Michel Autebert , Lenguas algebraicas , Masson,1987, 278  p. ( ISBN  978-2-225-81087-9 )
• (en) Wilhelm Magnus , Abraham Karrass y Donald Solitar , Teoría combinatoria de grupos. Presentaciones de grupos en términos de generadores y relaciones , Publicaciones de Dover ,2004, 444  p. ( ISBN  0-486-43830-9 , leer en línea )Reimpresión de la segunda edición, 1976

Notas y referencias

1. La terminología "bilateral" no es frecuente: en inglés, a menudo se usan "  palabras Dyck de dos caras  ". Jacques Labelle ( Quebec Annals of Mathematical Sciences vol. 17, n o  1, 1993) utiliza explícitamente el término "bilateral" Jacques Sakarovitch llamó "palabra Dyck" a las palabras de dos caras y "palabra de Shamir" a las palabras Dyck. Los matemáticos, en la teoría combinatoria de grupos, solo conocen palabras bilaterales y omiten el adjetivo.

Artículos relacionados

• Gramática formal
• Jerarquía de Chomsky
• Monoide sintáctico
• Noam Chomsky
• Marcel-Paul Schützenberger
• Número de catalán

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">