Trætilsætnings grammatik

Tree -adjoining grammatik TAG ) er en formel grammatik opfundet af Aravind Joshi ( engelsk  Denne grammatik generaliserer den kontekstfrie grammatik ved, at de elementære enheder i slutningsreglerne er træer, ikke individuelle tegn. Således definerer grammatikken reglerne for udskiftning af træknuder med undertræer (se træ i grafteori og træ i datalogi ).

Historie

TAG opstod som et resultat af forskning udført af Joshi og hans elever i en familie af tillægsgrammatikker [1] . Vedhæftede grammatikker er velegnede til at analysere sætninger, der indeholder et hovedord og mange afhængige ord, der indsnævrer betydningen af ​​hovedordet (f.eks. "et meget stort hus"). Men de karakteriserer ikke klart sætninger, hvor ikke et eneste ord kan bære hele strukturens funktion. Det samme gælder grammatik med sætningsstruktur . I 1969 introducerede Joshi en familie af grammatikker, der udnyttede denne komplementaritet ved at blande to typer regler. Denne familie er ikke en del af Chomsky-hierarkiet [2] og tilhører svagt kontekstfølsomme grammatikker , det vil sige med hensyn til genererende egenskaber er den stærkere end kontekstfri grammatik , men svagere end kontekstfølsomme [3] . Træadditionsgrammatikker er svagt ækvivalente med lineære indekserede grammatikker , kombinatoriske kategoriske grammatikker og overskriftsgrammatikker [4] (for enhver træadditionsgrammatik kan man konstruere en tilsvarende grammatik fra enhver af disse tre familier, der vil generere de samme strenge).

Beskrivelse

En TAG-regel er et træ med en bladknude, hvortil et ord (LTAG) kan knyttes.

Der er to typer træer: "initial" (ofte omtalt som ' ') og "hjælpetræer" (' '). De indledende træer repræsenterer sætningens hovedvalenser, mens hjælpetræerne tillader brugen af ​​rekursion [5] . Hjælpetræer har topknuden og bladknuden markeret med det samme symbol.

Udskiftninger starter fra det oprindelige træ og foretages ved substitution eller tilføjelse . En erstatning erstatter en node med et træ, hvis topknude er mærket med det samme symbol som det, der udskiftes. Append indsætter et hjælpeundertræ i midten af ​​træet [6] . Et hjælpetræ skal mærkes med samme etiket som den node, det er knyttet til.

Noter

  1. ↑ Joshi, Aravind; S.R. Kosaraju, H. Yamada. Strengtillægsgrammatikker  (neopr.) . — Proceedings tiende årlige symposium om automatteori, Waterloo, Canada, 1969.
  2. ↑ Joshi, Aravind. Egenskaber ved formelle grammatikker med blandede typer regler og deres sproglige relevans  (engelsk)  : tidsskrift. - Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sverige, 1969.
  3. ↑ Joshi, Aravind. Hvor meget kontekstfølsomhed er nødvendig for at karakterisere strukturelle beskrivelser // Natural Language Processing: Theoretical, Computational, and Psychological Perspectives  (engelsk) / D. Dowty, L. Karttunen og A. Zwicky, (red.). - New York, NY: Cambridge University Press , 1985. - S. 206-250.
  4. ↑ Vijay-Shanker, K. og Weir, David J. 1994. Equivalence of Four Extensions of Context-Free Grammars . Mathematical Systems Theory 27(6): 511-546.
  5. ↑ Jurafsky, Daniel; James H. Martin. Tale- og sprogbehandling  (ubestemt) . - Upper Saddle River, NJ: Prentice Hall , 2000. - s  . 354 .
  6. ↑ Joshi, Aravind; Owen Rambow (2003). "En formalisme for afhængighedsgrammatik baseret på trætilstødende grammatik" (PDF) . Proceedings of the Conference on Meaning-Text Theory . Forældet parameter brugt |coauthors=( hjælp ) Arkiveret 29. november 2020 på Wayback Machine

Links

På engelsk: