Gramàtica de concatenació de rang

De la Viquipèdia, l'enciclopèdia lliure

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]

Definició formal[modifica]

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ó
  • és el predicat nominal inicial i verifica que
  • és un conjunt infinit de clàusules de la forma on son predicats de la forma on i

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[modifica]

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[modifica]

  1. Boullier, Pierre «Proposal for a Natural Language Processing Syntactic Backbone». Technical report - INRIA Rocquencourt, Gen 1998.
  2. 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.
  3. Laura., Kallmeyer,. Parsing beyond context-free grammars. Heidelberg: Springer, 2010. ISBN 9783642148460.