Gramática de concatenación de rangos

La gramática de concatenación de rangos (RCG) es un formalismo gramatical desarrollado por Pierre Boullier ^[1] en 1998 como un intento de caracterizar una serie de fenómenos del lenguaje natural, como los números chinos y la codificación del orden de las palabras en alemán , que están fuera de los límites del lenguaje suave. lenguajes sensibles al contexto . ^[2]

Desde un punto de vista teórico, cualquier lenguaje que pueda analizarse en tiempo polinómico pertenece al subconjunto de RCG llamado gramáticas de concatenación de rango positivo, y recíprocamente. ^[4]

Aunque pretenden ser una variante de las gramáticas de movimiento literal (LMG) de Groenink , las RCG tratan el proceso gramatical más como una prueba que como una producción. Mientras que los LMG producen una cadena terminal a partir de un predicado inicial, los RCG tienen como objetivo reducir un predicado inicial (que predica una cadena terminal) a una cadena vacía, lo que constituye una prueba de la pertenencia de las cadenas terminales al lenguaje.

Descripción

Definicion formal

Una gramática de concatenación de rango positivo (PRCG) es una tupla , donde: ${\displaystyle G=(N,~T,~V,~S,~P)}$

• ${\displaystyle N}$, y son conjuntos finitos disjuntos de (respectivamente) nombres de predicados , símbolos terminales y nombres de variables . Cada nombre de predicado tiene una aridad asociada dada por la función . ${\displaystyle T}$ ${\displaystyle V}$ ${\displaystyle \dim :N\rightarrow \mathbb {N} \setminus \{0\}}$
• ${\displaystyle S\in N}$es el nombre del predicado inicial y verificar . ${\displaystyle \dim(S)=1}$
• ${\displaystyle P}$es un conjunto finito de cláusulas de la forma , donde son predicados de la forma con y . ${\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}}$ ${\displaystyle \psi _{i}}$ ${\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}$ ${\displaystyle A_{i}\in N}$ ${\displaystyle \alpha _{i}\in (T\cup V)^{\star }}$

Una gramática de concatenación de rango negativo (NRCG) se define como una PRCG, pero con la adición de que algunos predicados que aparecen en el lado derecho de una cláusula pueden tener la forma . Estos predicados se denominan predicados negativos . ${\displaystyle {\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}}$

Una gramática de concatenación de rangos es positiva o negativa. Aunque los PRCG son técnicamente NRCG, ​​los términos se utilizan para resaltar la ausencia (PRCG) o la presencia (NRCG) de predicados negativos.

Un rango en una palabra es un par , con , donde es la longitud de . Las variables se vinculan a rangos, no a cadenas arbitrarias de no terminales. Se pueden concatenar dos rangos y iff , y entonces tenemos: . Al crear una instancia de una cláusula, donde un argumento consta de varios elementos de , sus rangos deben concatenarse. ${\displaystyle w\in T^{\star }}$ ${\displaystyle \langle l,r\rangle _{w}}$ ${\displaystyle 0\leq l\leq r\leq n}$ ${\displaystyle n}$ ${\displaystyle w}$ ${\displaystyle \langle l_{1},r_{1}\rangle _{w}}$ ${\displaystyle \langle l_{2},r_{2}\rangle _{w}}$ ${\displaystyle r_{1}=l_{2}}$ ${\displaystyle \langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2}\rangle _{w}}$ ${\displaystyle T\cup V}$

Para una palabra con , la notación con puntos para rangos es: . ${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$ ${\displaystyle w_{i}\in T}$ ${\displaystyle \langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}}$

Reconocimiento de cuerdas

Las cadenas de predicados que se reescriben representan restricciones que la cadena que se prueba debe satisfacer (si es positiva) o, en el caso de predicados negativos, no satisfacer. El orden de los predicados es irrelevante. Los pasos de reescritura equivalen a reemplazar una restricción por cero o más restricciones más simples.

Al igual que las LMG, las cláusulas RCG tienen el esquema general , donde en un RCG es una cadena vacía o una cadena de predicados. Los argumentos consisten en cadenas de símbolos terminales y/o símbolos variables, cuyo patrón coincide con los valores reales de los argumentos como en LMG. Las variables adyacentes constituyen una familia de coincidencias con particiones, de modo que el argumento , con dos variables, coincide con la cadena literal de tres maneras diferentes: . Esto daría lugar a tres ejemplificaciones diferentes de la cláusula que contiene ese argumento . ${\displaystyle A(x_{1},...,x_{n})\to \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle x_{i}}$ ${\displaystyle xy}$ ${\displaystyle ab}$ ${\displaystyle x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon }$ ${\displaystyle xy}$

Los términos predicados vienen en dos formas, positivos (que producen la cadena vacía en caso de éxito) y negativos (que producen la cadena vacía en caso de error/si el término positivo no produce la cadena vacía). Los términos negativos se indican de la misma manera que los términos positivos, con una barra superior, como en . ${\displaystyle {\overline {A(x_{1},...,x_{n})}}}$

La semántica de reescritura de los RCG es bastante simple, idéntica a la semántica correspondiente de las LMG. Dada una cadena de predicado , donde los símbolos son cadenas terminales, si hay una regla en la gramática que indica que la cadena de predicado coincide, la cadena de predicado se reemplaza por , sustituyendo las variables coincidentes en cada . ${\displaystyle A(\alpha _{1},...,\alpha _{n})}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle A(x_{1},...,x_{n})\to \beta }$ ${\displaystyle \beta }$ ${\displaystyle x_{i}}$

Por ejemplo, dada la regla donde y son símbolos variables y y son símbolos terminales, la cadena de predicado se puede reescribir como , porque coincide con cuando . De manera similar, si existiera una regla , podría reescribirse como . ${\displaystyle A(x,ayb)\to B(axb,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle A(a,abb)}$ ${\displaystyle B(aab,b)}$ ${\displaystyle A(a,abb)}$ ${\displaystyle A(x,ayb)}$ ${\displaystyle x=a,\ y=b}$ ${\displaystyle A(x,ayb)\to A(x,x)\ A(y,y)}$ ${\displaystyle A(a,abb)}$ ${\displaystyle A(a,a)\ A(b,b)}$

Una prueba/reconocimiento de una cadena se realiza mostrando que produce la cadena vacía. Para los pasos de reescritura individuales, cuando son posibles múltiples coincidencias de variables alternativas, se considera cualquier reescritura que pueda llevar a que toda la prueba tenga éxito. Por lo tanto, si hay al menos una forma de producir la cadena vacía a partir de la cadena inicial , la prueba se considera exitosa, independientemente de cuántas otras formas de fallar existan. ${\displaystyle \alpha }$ ${\displaystyle S(\alpha )}$ ${\displaystyle S(\alpha )}$

Ejemplo

Los RCG son capaces de reconocer el lenguaje de índice no lineal de la siguiente manera: ${\displaystyle \{www:w\in \{a,b\}^{*}\}}$

Sean x, y y z símbolos variables:

$${\displaystyle {\begin{aligned}S(xyz)&\to A(x,y,z)\\A(ax,ay,az)&\to A(x,y,z)\\A(bx,by,bz)&\to A(x,y,z)\\A(\epsilon ,\epsilon ,\epsilon )&\to \epsilon \end{aligned}}}$$

abbabbabb

${\displaystyle S(abbabbabb)\Rightarrow A(abb,abb,abb)\Rightarrow A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

O bien, usando la notación de puntos más correcta para rangos:

${\displaystyle S(\bullet {}abbabbabb\bullet {})\Rightarrow A(\bullet {}abb\bullet {}abbabb,abb\bullet {}abb\bullet {}abb,abbabb\bullet {}abb\bullet {})\Rightarrow A(a\bullet {}bb\bullet {}abbabb,abba\bullet {}bb\bullet {}abb,abbabba\bullet {}bb\bullet {})}$ ${\displaystyle \Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

Para una cadena de letras, existen diferentes instancias de esa primera cláusula, pero solo la que hace que todas las letras permitan que la derivación llegue a . ${\displaystyle 3n}$ ${\displaystyle {\binom {3n+2}{2}}={\frac {(3n+2)(3n+1)}{2}}}$ ${\displaystyle x,y,z}$ ${\displaystyle n}$ ${\displaystyle \epsilon }$

Propiedades

Cada gramática libre de contexto (CFG) se puede convertir en una gramática de concatenación de rangos:

• Para cada no terminal del CFG, el RCG tiene un predicado de aridad . ${\displaystyle A}$ ${\displaystyle 1}$ ${\displaystyle A(x)}$
• Para cada regla del CFG , el RCG tiene . ${\displaystyle A\to BC}$ ${\displaystyle A(xy)\to B(x)C(y)}$
• Para cada regla CFG (donde es terminal), el RCG tiene . ${\displaystyle A\to a}$ ${\displaystyle a}$ ${\displaystyle A(a)\to \epsilon }$

La intersección y unión de dos lenguajes de concatenación de rangos son lenguajes de concatenación de rangos triviales:

• Para la intersección de y , tienes . ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S(x)\to A(x)B(x)}$
• Para la unión de y , tienes y . ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle S(x)\to A(x)}$ ${\displaystyle S(x)\to B(x)}$

Los lenguajes de concatenación de rango posiblemente negativo también están cerrados bajo complemento de conjuntos.

Una consecuencia de lo anterior es que es indecidible si un lenguaje de concatenación de rango (positivo) no está vacío, porque es indecidible si la intersección de dos lenguajes libres de contexto no está vacía. Por tanto, las gramáticas de concatenación de rangos no son generativas.

Referencias

1. Boullier, Pierre (enero de 1998). Propuesta de una columna vertebral sintáctica de procesamiento del lenguaje natural (PDF) (Reporte técnico). vol. 3342. INRIA Rocquencourt (Francia).
2. Pierre Boullier (1999). "Gramáticas de números chinos, MIX, codificación y concatenación de rangos" (PDF) . Proc. EACL . págs. 53–60. Archivado desde el original (PDF) el 15 de mayo de 2003.
3. Eberhard Bertsch y Mark-Jan Nederhof (octubre de 2001). "Sobre la complejidad de algunas extensiones del análisis RCG" (PDF) . Actas del Séptimo Taller Internacional sobre Tecnologías de Análisis (Beijing) . págs. 66–77.
4. Laura Kallmeyer (2010). Análisis más allá de las gramáticas libres de contexto . Medios de ciencia y negocios de Springer. pag. 37.ISBN​ 978-3-642-14846-0.citando a Bertsch, Nederhof (2001) ^[3]