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\to \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\to {\psi }_1\dots {\psi }_m$ on ${\psi }_i$son predicats de la forma $A_i({\alpha }_1,\dots ,{\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,\dots ,{\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 $⟨l,r{⟩}_w$amb $0\le l\le r\le n$, on $n$és la longitud de $w$. Dos rangs $⟨l_1,r_1{⟩}_w$i $⟨l_2,r_2{⟩}_w$es poden concatenar si i només si $r_1=l_2$i llavors es te $⟨l_1,r_1{⟩}_w\cdot ⟨l_2,r_2{⟩}_w=⟨l_1,r_2{⟩}_w$.

Per una paraula $w=w_1{w}_2\dots w_n$ amb $w_i\in T$, la notació de punt per rang és $⟨l,r{⟩}_w=w_1\dots w_{l-1}\bullet w_l\dots w_{r-1}\bullet w_r\dots 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(ϵ,ϵ,ϵ)\to ϵ$

La prova per abbabbabb és:

$S(abbabbabb)\Rightarrow A(abb,abb,abb)\Rightarrow A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(ϵ,ϵ,ϵ)\Rightarrow ϵ$

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