Gramàtica de concatenació de rang

Les gramàtiques de concatenació de rang (RCG per les seves sigles en anglès) és un formalisme de gramàtica desenvolupat per Pierre Boullier el 1998 per intentar caracteritzar uns fenòmens de llenguatges naturals com els números xinesos o l'ordre de les paraules en alemany, que cauen fora dels límits de les gramàtiques lleugerament sensibles al context.

Des d'un punt de vista teòric, qualsevol llenguatge que es pot analitzar en un temps polinòmic pertany al subconjunt de les RCG anomenat gramàtiques positives de concatenació de rang i viceversa.

Definició formal

Una gramàtica positiva de concatenació de rang (PRCG) és una tupla $G=(N,~T,~V,~S,~P)$, on:

• $N,T{\text{ i }}V$son conjunts finits disjunts de predicats nominals, símbols terminals i noms de variables respectivament. Cada predicat nominal té una aritat associada donada per la funció $\dim :N\rightarrow \mathbb {N} \setminus \{0\}$
• $S\in N$és el predicat nominal inicial i verifica que $\dim(S)=1$
• $P$ és un conjunt infinit de clàusules de la forma $\psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}$ on $\psi _{i}$son predicats de la forma $\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})$on $A_{i}\in N$i $\alpha _{i}\in (T\cup V)^{\star }$

Una gramàtica negativa de concatenació de rang (NRCG) es defineix com una positiva amb l'afegit que alguns predicats que apareixen a la part dreta de les clàusules poden ser de la forma ${\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}$. Aquests predicats s'anomenen predicats negatius.

Una gramàtica de concatenació de rang o bé és positiva o negativa. Es denota l'absència de predicats negatius com PRCG i les que en tenen com NRCG.

Un rang d'una paraula $w\in T^{\star }$és una parella $\langle l,r\rangle _{w}$amb $0\leq l\leq r\leq n$, on $n$és la longitud de $w$. Dos rangs $\langle l_{1},r_{1}\rangle _{w}$i $\langle l_{2},r_{2}\rangle _{w}$es poden concatenar si i només si $r_{1}=l_{2}$i llavors es te $\langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2}\rangle _{w}$.

Per una paraula $w=w_{1}w_{2}\ldots w_{n}$ amb $w_{i}\in T$, la notació de punt per rang és $\langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}$.

Exemple

Les RCG poden reconèixer el llenguatge indexat no lineal $\{www:w\in \{a,b\}^{*}\}$com segueix:

Siguin, $x,y,{\text{ i }}z$símbols 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 prova per abbabbabb és:

$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 en notació de punt per rangs:$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$