Gramática de concatenación de rango

Gramática de concatenación de rango (GCR) es una gramática formal desarrollada por Pierre Boullier en 1998 como un intento de caracterizar una serie de fenómenos del lenguaje natural, tales como los números chinos y el orden aleatorio de palabras alemanas, los cuales están fuera de los límites de los formalismos gramáticos sensibles al contexto.​

Desde un punto de vista teórico, cualquier lenguaje que pueda ser analizado en tiempo polinómico pertenece al subconjunto de las GCRs llamado gramáticas de concatenación de rango positivo, y recíprocamente.​

Aunque pretende ser una variante de las Gramáticas del Movimiento Literal de Groenink (GML), las GCRs tratan el proceso gramatical más como una prueba que como una producción. Mientras que las GMLs producen una cadena terminal a partir de un predicado inicial, las GCRs tienen como objetivo reducir un predicado inicial a la cadena vacía, lo que constituye una prueba de la pertenencia de las cadenas terminales al lenguaje.

Descripción

Definición formal

Una Gramática de Concatenación de Rango Positiva (GCRP) es una tupla $G=(N,~T,~V,~S,~P)$, donde:

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

Una Gramática de Concatenación de Rango Negativa (GCRN) está definida como GCRP, pero con la adición de que algunos predicados que ocurren en el lado derecho de una cláusula pueden tener la forma ${\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}$. Such predicates are called negative predicates.

Una Gramática de Concatenación de Rango es positiva o negativa. Aunque las GCRPs son técnicamente GCRNs, los términos se utilizan para resaltar la ausencia (GCRP) o la presencia (GCRN) de los predicados negativos.

Un rango en una palabra $w\in T^{\star }$ es un par $\langle l,r\rangle _{w}$, con $0\leq l\leq r\leq n$, donde $n$ es la longitud de $w$. Dos rangos $\langle l_{1},r_{1}\rangle _{w}$ y $\langle l_{2},r_{2}\rangle _{w}$ pueden ser concatenados si $r_{1}=l_{2}$, y entonces tenemos: $\langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2}\rangle _{w}$.

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

Como en las GMLs, las cláusulas de las GCR tienen el esquema general $A(x_{1},...,x_{n})\to \alpha$, donde en una GCR, $\alpha$ es la cadena vacía o una cadena de predicados. Los argumentos $x_{i}$ consisten en cadenas de símbolos terminales y / o símbolos variables, cuyo patrón coincide con los valores de los argumentos reales como en las GMLs. Las variables adyacentes constituyen una familia de coincidencias contra particiones, de modo que el argumento $xy$, con dos variables, coincide con la cadena literal $ab$ en tres formas diferentes: $x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon$.

Los términos predicados vienen en dos formas, positiva (la cual produce la cadena vacía en caso de éxito), y negativa (la cual produce 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 términos positivos, con una barra superior, como en ${\overline {A(x_{1},...,x_{n})}}$.

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

Por ejemplo, dada la regla $A(x,ayb)\to B(axb,y)$, donde $x$ y $y$ son símbolos variables y $a$ y $b$ son símbolos terminales, la cadena predicado $A(a,abb)$ puede ser reescrita como $B(aab,b)$, porque $A(a,abb)$ coincide con $A(x,ayb)$ cuando $x=a,\ y=b$. De forma similar, si existiera una regla $A(x,ayb)\to A(x,x)\ A(y,y)$, $A(a,abb)$ puede ser reescrita como $A(a,a)\ A(b,b)$.

Un reconocimiento/prueba de una cadena $\alpha$ se realiza mostrando que $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 podría conducir a que toda la prueba tenga éxito. Por lo tanto, si hay al menos una manera de producir la cadena vacía de la cadena inicial $S(\alpha )$, la prueba se considera un éxito, independientemente de cuántas otras maneras de fallar existan.

Ejemplo

GCRs son capaces de reconocer el lenguaje de índice no lineal $\{www:w\in \{a,b\}^{*}\}$ de la siguiente manera: Dejando x, y, y z ser símbolos variables:

$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$

La prueba para abbabbabb es entonces:

$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, utilizando la notación puntual más correcta para rangos:

$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 {})$ $\Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon$

Referencias

• Datos: Q7292697