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 confusión del orden de las palabras en alemán , que están fuera de los límites de los lenguajes ligeramente sensibles al contexto . ^[2]

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

Aunque se concibieron como 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 las LMG producen una cadena terminal a partir de un predicado inicial, las RCG apuntan a reducir un predicado inicial (que es el predicado de una cadena terminal) a la cadena vacía, que constituye una prueba de la pertenencia de la cadena terminal al lenguaje.

Descripción

Definición 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 predicado , símbolos terminales y nombres de variable . 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 de inicio y verificación . ${\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 el añadido de que algunos predicados que aparecen en el lado derecho de una cláusula pueden tener la forma . Dichos predicados se denominan predicados negativos . ${\displaystyle {\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}}$

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

Un rango en una palabra es una pareja , con , donde es la longitud de . Las variables se vinculan a rangos, no a cadenas arbitrarias de elementos no terminales. Dos rangos y se pueden concatenar si y solo si , y entonces tenemos: . Al crear una instancia de una cláusula, donde un argumento consta de múltiples 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 de 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 cadenas

Las cadenas de predicados que se reescriben representan restricciones que la cadena que se está probando 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 una RCG, es la cadena vacía o una cadena de predicados. Los argumentos consisten en cadenas de símbolos terminales y/o símbolos de variables, que coinciden con los valores de argumentos reales 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 formas diferentes: . Esto daría lugar a tres instancias 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 se presentan 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 o si el término positivo no produce la cadena vacía). Los términos negativos se denotan de la misma forma que los términos positivos, con una barra superior, como en . ${\displaystyle {\overline {A(x_{1},...,x_{n})}}}$

La semántica de reescritura para los RCG es bastante simple, idéntica a la semántica correspondiente de los 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 de variable y y son símbolos terminales, la cadena de predicado se puede reescribir como , porque coincide cuando . De manera similar, si hubiera una regla , se podría reescribir 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)}$

La prueba o el 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 hacer que la prueba completa 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 un éxito, 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\}^{*}\}}$

Sea x, y, z símbolos variables: La prueba para abbabbabb es entonces $${\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}}}$$

${\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, utilizando la notación punteada 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, hay diferentes instancias de esa primera cláusula, pero solo aquella que hace que todas las letras sean iguales permite 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 CFG , el RCG tiene . ${\displaystyle A\to BC}$ ${\displaystyle A(xy)\to B(x)C(y)}$
• Para cada regla CFG (donde 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, trivialmente, lenguajes de concatenación de rangos:

• 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)}$

Posiblemente los lenguajes de concatenación de rango negativo también estén cerrados bajo el complemento de conjunto.

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

Referencias

1. Boullier, Pierre (enero de 1998). Propuesta de una estructura sintáctica para el procesamiento del lenguaje natural (PDF) (informe técnico). Vol. 3342. INRIA Rocquencourt (Francia).
2. Pierre Boullier (1999). "Números chinos, MIX, mezcla y gramáticas de 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 sintáctico RCG" (PDF) . Actas del Séptimo Taller Internacional sobre Tecnologías de Análisis Sintáctico (Beijing) . pp. 66–77.
4. Laura Kallmeyer (2010). Análisis sintáctico más allá de las gramáticas independientes del contexto . Springer Science & Business Media. pág. 37. ISBN 978-3-642-14846-0.citando a Bertsch, Nederhof (2001) ^[3]