Древесно-соседственные грамматики: формализм и свойства

Grammar formalism
Tree adjoining grammar (TAG) is a grammar formalism defined by Aravind Joshi. Tree adjoining grammars are somewhat similar to context free grammars, but the elementary unit of rewriting is the tree rather than the symbol. Whereas context free grammars have rules for rewriting symbols as strings of other symbols, tree adjoining grammars have rules for rewriting the nodes of trees as other trees (see tree (graph theory) and tree (data structure)).

The rules in a TAG are trees with a special leaf node known as the foot node, which is anchored to a word. There are two types of basic trees in TAG: initial trees (often represented as '') and auxiliary trees (''). Initial trees represent basic valency relations, while auxiliary trees allow for recursion. Auxiliary trees have the root (top) node and foot node labeled with the same symbol. A derivation starts with an initial tree, combining via either substitution or adjunction. Substitution replaces a frontier node with another tree whose top node has the same label. The root/foot label of the auxiliary tree must match the label of the node at which it adjoins. Adjunction can thus have the effect of inserting an auxiliary tree into the center of another tree. indexed or context sensitive grammars. A TAG can describe the language of squares (in which some arbitrary string is repeated), and the language This type of processing can be represented by an embedded pushdown automaton. Languages with cubes (i. e. triplicated strings) or with more than four distinct character strings of equal length cannot be generated by tree adjoining grammars. For these reasons, tree adjoining grammars are often described as mildly context sensitive. These grammar classes are conjectured to be powerful enough to model natural languages while remaining efficiently parsable in the general case.

Vijay Shanker and Weir (1994) demonstrate that linear indexed grammars, combinatory categorial grammar, tree adjoining grammars, and head grammars are weakly equivalent formalisms, in that they all define the same string languages.

Lexicalized tree adjoining grammars (LTAG) are a variant of TAG in which each elementary tree (initial or auxiliary) is associated with a lexical item. A lexicalized grammar for English has been developed by the XTAG Research Group of the Institute for Research in Cognitive Science at the University of Pennsylvania.