gramática de concatenación de rangos

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

• ${\displaystyle N}$,${\displaystyle T}$y${\displaystyle V}$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 \dim :N\rightarrow \mathbb {N} \setminus \{0\}}$.
• ${\displaystyle S\in N}$es el nombre del predicado de inicio y verificar${\displaystyle \dim(S)=1}$.
• ${\displaystyle P}$es un conjunto finito de cláusulas de la forma${\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}}$, donde el${\displaystyle \psi _{i}}$son predicados de la forma${\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}$con${\displaystyle A_{i}\in N}$y${\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${\displaystyle {\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}}$Estos predicados se denominan predicados negativos .

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

Una gama en una palabra${\displaystyle w\in T^{\star }}$es una pareja${\displaystyle \langle l,r\rangle _ {w}}$, con${\displaystyle 0\leq l\leq r\leq n}$, dónde${\displaystyle n}$es la longitud de${\displaystyle w}$Las variables se vinculan a rangos, no a cadenas arbitrarias de no terminales. Dos rangos${\displaystyle \langle l_{1},r_{1}\rangle _{w}}$y${\displaystyle \langle l_{2},r_{2}\rangle _{w}}$se pueden concatenar si y solo si${\displaystyle r_{1}=l_{2}}$y entonces tenemos:${\displaystyle \langle l_{1},r_{1}\rangle _ {w}\cdot \langle l_ {2},r_ {2}\rangle _ {w}=\langle l_ {1},r_ {2}\rangle _ {w}}$. Al instanciar una cláusula, donde un argumento consta de múltiples elementos de${\displaystyle T\cup V}$, sus rangos deben concatenarse.

Por una palabra${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$, con${\displaystyle w_{i}\in T}$, la notación con puntos para rangos es:${\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}}$.

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

Al igual que las cláusulas LMG, las cláusulas RCG tienen el esquema general.${\displaystyle A(x_{1},...,x_{n})\to \alpha }$, donde en un RCG,${\displaystyle \alpha }$es o bien la cadena vacía o una cadena de predicados. Los argumentos${\displaystyle x_{i}}$Consisten en cadenas de símbolos terminales y/o símbolos de variables, que coinciden con patrones contra valores de argumentos reales como en LMG. Las variables adyacentes constituyen una familia de coincidencias contra particiones, de modo que el argumento${\displaystyle xy}$, con dos variables, coincide con la cadena literal${\displaystyle ab}$de tres maneras diferentes:${\displaystyle x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon }$Esto daría lugar a tres instancias diferentes de la cláusula que contiene ese argumento.${\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 fallo/si el término positivo no produce la cadena vacía). Los términos negativos se denotan igual que los positivos, con una barra superior, como en${\displaystyle {\overline {A(x_{1},...,x_{n})}}}$.

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

Por ejemplo, dada la regla${\displaystyle A(x,ayb)\to B(axb,y)}$, dónde${\displaystyle x}$y${\displaystyle y}$son símbolos variables y${\displaystyle a}$y${\displaystyle b}$son símbolos terminales, la cadena de predicados${\displaystyle A(a,abb)}$puede reescribirse como${\displaystyle B(aab,b)}$, porque${\displaystyle A(a,abb)}$partidos${\displaystyle A(x,ayb)}$cuando${\displaystyle x=a,\ y=b}$. De manera similar, si hubiera una regla${\displaystyle A(x,ayb)\to A(x,x)\ A(y,y)}$,${\displaystyle A(a,abb)}$podría reescribirse como${\displaystyle A(a,a)\ A(b,b)}$.

Una prueba/reconocimiento de una cadena${\displaystyle \alpha }$se hace demostrando que${\displaystyle S(\alpha )}$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${\displaystyle S(\alpha )}$La prueba se considera un éxito, independientemente de cuántas otras formas de fracasar existan.