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.[1][2]
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.[3]
Una gramàtica positiva de concatenació de rang (PRCG) és una tupla
, on:
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ó ![{\displaystyle \dim :N\rightarrow \mathbb {N} \setminus \{0\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f434fa2271dea42c671f64effdfe4e28d1662cd)
és el predicat nominal inicial i verifica que ![{\displaystyle \dim(S)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44458ffba908aaeca4405d18fb52fc4634ff3377)
és un conjunt infinit de clàusules de la forma
on
son predicats de la forma
on
i ![{\displaystyle \alpha _{i}\in (T\cup V)^{\star }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca944a53d46ee412028d5f15983f89cb0d57d60a)
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
. 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
és una parella
amb
, on
és la longitud de
. Dos rangs
i
es poden concatenar si i només si
i llavors es te
.
Per una paraula
amb
, la notació de punt per rang és
.
Exemple
Les RCG poden reconèixer el llenguatge indexat no lineal
com segueix:
Siguin,
símbols variables:
La prova per abbabbabb és:
o en notació de punt per rangs:
Referències
- ↑ Boullier, Pierre «Proposal for a Natural Language Processing Syntactic Backbone». Technical report - INRIA Rocquencourt, Gen 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.
|
---|
|
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. |