Gramatika sousedící se stromem

Gramatika sousedící se stromem (TAG) je gramatický formalismus definovaný Aravindem Joshim, který se často používá ve výpočetní lingvistice a zpracování přirozeného jazyka. Gramatiky sousedící se stromem jsou trochu podobné bezkontextovým gramatikám, ale elementární jednotkou přepisu je spíše strom než symbol. Zatímco bezkontextové gramatiky mají pravidla pro přepisování symbolů jako řetězců jiných symbolů, gramatiky sousedící se stromem mají pravidla pro přepisování uzlů stromů jako jiných stromů (viz strom (teorie grafů) a stromová datová struktura).

Pravidla v TAG (známé jako pomocné stromy) jsou stromy se speciálním listovým uzlem známým jako nohový uzel. Kořenový (horní) uzel a nohový uzel musí být označeny stejným symbolem.

Odvození TAG začíná počátečním stromem (analogicky k počátečnímu symbolu v bezkontextové gramatice). Přepis se provádí přidáním, kdy je pomocný strom přiložen k uzlu (typicky ne-listovému uzlu) v aktuálním stromě. Kořenový/stopový štítek pomocného stromu musí odpovídat štítku uzlu, na kterém přiléhá. Tato operace rozdělí uzel, který je cílem přidání, na horní a spodní polovinu; horní polovina je připojena ke kořenu přilehlého stromu, zatímco spodní polovina je připojena k dolnímu uzlu přilehlého stromu.

Jedná se o nejzákladnější variantu TAG; nejběžnější varianta přidává další přepisovací operaci zvanou substituce a další varianty umožňují vícesložkové stromy, stromy s více nohovými uzly a další rozšíření.

Stromově sousedící gramatiky jsou často popisovány jako „mírně kontextově citlivé“, což znamená, že mají určité vlastnosti, které je činí výkonnějšími (ve smyslu slabé generativní kapacity) než bezkontextové gramatiky, ale méně výkonnými než kontextově citlivé gramatiky, jak jsou definovány v Chomského hierarchii. Mírně kontextově citlivé gramatiky jsou (někdy se to odhaduje) dostatečně výkonné, aby modelovaly gramatiky přirozených jazyků, zatímco v obecném případě zůstávají efektivně zpracovatelné.[Jak odkazovat a odkazovat na shrnutí nebo text]