Grammatica ad albero adiacente - Tree-adjoining grammar

Tree-adjoining grammar ( TAG ) è un formalismo grammaticale definito da Aravind Joshi . Le grammatiche adiacenti agli alberi sono in qualche modo simili alle grammatiche libere dal contesto , ma l'unità elementare di riscrittura è l'albero piuttosto che il simbolo. Mentre le grammatiche prive di contesto hanno regole per riscrivere i simboli come stringhe di altri simboli, le grammatiche adiacenti ad albero hanno regole per riscrivere i nodi degli alberi come altri alberi (vedere albero (teoria dei grafi) e albero (struttura dei dati) ).

Storia

TAG ha avuto origine dalle indagini di Joshi e dei suoi studenti sulla famiglia delle grammatiche aggiunte (AG), la "grammatica degli archi" di Zellig Harris . Gli AG gestiscono le proprietà esocentriche del linguaggio in modo naturale ed efficace, ma non hanno una buona caratterizzazione delle costruzioni endocentriche ; il contrario è vero per la riscrittura delle grammatiche o la grammatica della struttura delle frasi (PSG). Nel 1969, Joshi ha introdotto una famiglia di grammatiche che sfrutta questa complementarità mescolando i due tipi di regole. Poche regole di riscrittura molto semplici sono sufficienti per generare il vocabolario delle stringhe per le regole di aggiunta. Questa famiglia è distinta dalla gerarchia di Chomsky-Schützenberger ma la interseca in modi interessanti e linguisticamente rilevanti. Le stringhe centrali e le stringhe aggiunte possono anche essere generate da una grammatica delle dipendenze , evitando completamente i limiti dei sistemi di riscrittura.

Descrizione

Le regole in un TAG sono alberi con uno speciale nodo foglia noto come nodo del piede , che è ancorato a una parola. Ci sono due tipi di alberi di base in TAG: alberi iniziali (spesso rappresentati come " ") e alberi ausiliari (" "). Gli alberi iniziali rappresentano le relazioni di valenza di base, mentre gli alberi ausiliari consentono la ricorsione. Gli alberi ausiliari hanno il nodo radice (superiore) e il nodo del piede etichettati con lo stesso simbolo. Una derivazione inizia con un albero iniziale, che si combina tramite sostituzione o aggiunta . La sostituzione sostituisce un nodo di frontiera con un altro albero il cui nodo superiore ha la stessa etichetta. L'etichetta radice / piede dell'albero ausiliario deve corrispondere all'etichetta del nodo a cui è adiacente. L'adattamento può quindi avere l'effetto di inserire un albero ausiliario al centro di un altro albero.

Altre varianti di TAG consentono alberi multicomponente , alberi con più nodi di piede e altre estensioni.

Complessità e applicazione

Grammatiche albero-adiacente sono più potenti (in termini di debole capacità generativa ) rispetto grammatiche context-free , ma meno potente di sistemi lineari non contestuali riscrittura , indicizzati o sensibili al contesto grammatiche.

Un TAG può descrivere la lingua dei quadrati (in cui viene ripetuta una stringa arbitraria) e la lingua . Questo tipo di elaborazione può essere rappresentato da un automa pushdown incorporato . Le lingue con cubi (cioè stringhe triplicate) o con più di quattro stringhe di caratteri distinte di uguale lunghezza non possono essere generate da grammatiche ad albero adiacenti.

Per questi motivi, le grammatiche adiacenti ad albero sono spesso descritte come leggermente sensibili al contesto . Si ipotizza che queste classi grammaticali siano abbastanza potenti da modellare linguaggi naturali pur rimanendo analizzabili in modo efficiente nel caso generale.

Equivalenze

Vijay-Shanker e Weir (1994) dimostrano che le grammatiche indicizzate lineari , la grammatica categoriale combinatoria, le grammatiche albero-adiacenti e le grammatiche dell'intestazione sono formalismi debolmente equivalenti , in quanto definiscono tutte le stesse lingue di stringa.

Lessicalizzato

Le grammatiche lessicalizzate ad albero adiacente (LTAG) sono una variante di TAG in cui ogni albero elementare (iniziale o ausiliario) è associato a un elemento lessicale. Una grammatica lessicalizzata per l'inglese è stata sviluppata dall'XTAG Research Group dell'Institute for Research in Cognitive Science presso l'Università della Pennsylvania.

Appunti

Riferimenti

link esterno