Fa összeadás nyelvtan

A fa melletti nyelvtan TAG ) egy formális nyelvtan , amelyet Aravind Joshi ( angol  Ez a nyelvtan általánosítja a környezetfüggetlen nyelvtant annyiban , hogy a következtetési szabályok elemi egységei fák, nem pedig egyedi karakterek. Így a nyelvtan meghatározza a fa csomópontjainak részfákkal való helyettesítésének szabályait (lásd fa a gráfelméletben és fa a számítástechnikában ).

Történelem

A TAG Joshi és tanítványai által végzett kutatás eredményeként jött létre a kiegészítõ nyelvtani családban [1] . A csatolás nyelvtan kiválóan alkalmas olyan kifejezések elemzésére, amelyek egy fő szót és sok függő szót tartalmaznak, amelyek szűkítik a fő szó jelentését (például "nagyon nagy ház"). Nem jellemzik azonban egyértelműen azokat a kifejezéseket, amelyekben egyetlen szó sem hordozhatja a teljes szerkezet funkcióját. Ugyanez vonatkozik a kifejezésszerkezetű nyelvtanra is . 1969-ben Joshi bevezetett egy nyelvtani családot, amely kétféle szabály keverésével kihasználta ezt a komplementaritást. Ez a család nem része a Chomsky-hierarchiának [2] , és a gyengén kontextusérzékeny nyelvtanokhoz tartozik , vagyis a tulajdonságok generálása szempontjából erősebb a kontextusmentes nyelvtanoknál , de gyengébb a kontextusérzékenyeknél [3] . A faösszeadási nyelvtanok gyengén ekvivalensek a lineárisan indexelt nyelvtanokkal , a kombinatorikus kategorikus nyelvtanokkal és a fejléc-nyelvtanokkal [4] (bármely faösszeadás nyelvtanhoz e három család bármelyikéből létrehozhatunk egy megfelelő nyelvtant, amely ugyanazokat a karakterláncokat hozza létre).

Leírás

A TAG-szabály egy fa levélcsomóponttal, amelyhez szó (LTAG) kapcsolható.

Kétféle fa létezik: "kezdeti" (gyakran '' -ként) és "kisegítő" (' '). A kezdeti fák a kifejezés fő vegyértékeit képviselik, míg a segédfák lehetővé teszik a rekurzió használatát [5] . A segédfák felső csomópontja és levélcsomópontja ugyanazzal a szimbólummal van jelölve.

A cserék a kezdeti fától indulnak, és helyettesítéssel vagy hozzáadással történnek . A csere lecseréli a csomópontot egy olyan fára, amelynek felső csomópontja ugyanazzal a szimbólummal van megjelölve, mint a lecserélt csomópont. Az Append beszúr egy segéd részfát a fa közepére [6] . A segédfát ugyanazzal a címkével kell ellátni, mint azt a csomópontot, amelyhez csatolva van.

Jegyzetek

  1. ↑ Joshi, Aravind; S. R. Kosaraju, H. Yamada. String  Adjunct Grammars (neopr.) . – Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Kanada, 1969.
  2. ↑ Joshi, Aravind. A vegyes típusú szabályokkal rendelkező formális nyelvtanok tulajdonságai és nyelvi relevanciája  (angolul)  : folyóirat. - Proceedings Third International Symposium on Computational Linguistics, Stockholm, Svédország, 1969.
  3. ↑ Joshi, Aravind. Mennyi kontextusérzékenység szükséges a szerkezeti leírások jellemzéséhez // Natural Language Processing: Theoretical, Computational, and Psychological Perspectives  (angol) / D. Dowty, L. Karttunen és A. Zwicky, (szerk.). - New York, NY: Cambridge University Press , 1985. - P. 206-250.
  4. ↑ Vijay-Shanker, K. és Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars . Matematikai rendszerelmélet 27(6): 511-546.
  5. ↑ Jurafsky, Daniel; James H. Martin. Beszéd- és nyelvfeldolgozás  (határozatlan idejű) . - Upper Saddle River, NJ: Prentice Hall , 2000. -  354. o .
  6. ↑ Joshi, Aravind; Owen Rambow (2003). „A függőségi nyelvtan formalizmusa a fa melletti nyelvtan alapján” (PDF) . A jelentés-szövegelméleti konferencia anyaga . Elavult használt paraméter |coauthors=( súgó ) Archiválva : 2020. november 29. a Wayback Machine -nél

Linkek

Angolul: