# 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(\bulletabbabbabb\bullet)\Rightarrow A(\bulletabb\bulletabbabb,abb\bulletabb\bulletabb,abbabb\bulletabb\bullet)\Rightarrow A(a\bulletbb\bulletabbabb,abba\bulletbb\bulletabb,abbabba\bulletbb\bullet)$

## Referències

* ↑ Boullier, Pierre «Proposal for a Natural Language Processing Syntactic Backbone». Technical report - INRIA Rocquencourt, 01-01-1998.
* ↑ Boullier, Pierre «Chinese Numbers, MIX, Scrambling, and Range Concatenation Grammars». EACL '99 Proceedings of the ninth conference on European chapter of the Association for Computational Linguistics. Association for Computational Linguistics [Stroudsburg, PA, USA], 1999, pàg. 53–60. DOI: 10.3115/977035.977044.
* ↑ Laura., Kallmeyer,. Parsing beyond context-free grammars. Heidelberg: Springer, 2010. ISBN 9783642148460.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :