Grammar, dominating

A type of formal grammar (cf. Grammar, formal) serving to generate strings together with derivation trees (cf. Syntactic structure). Formally, a dominating grammar can be defined as a context-free grammar (cf. Grammar, context-free) in which one of the occurrences of symbols on the right-hand side carries a special mark, except for rules of the type $I\to a$ where $I$ is the initial symbol and $a$ is a terminal symbol. The right-hand side of each such rule must contain not fewer than two symbol occurrences. The context-sensitive system corresponding to the derivation in such a grammar (cf. Grammar, context-sensitive) becomes hierarchic if the components "originating" from the marked occurrences of symbols on the right-hand side of the rules are considered to be the terminal components. Each string of the language generated by the grammar is represented by a "derivation" tree, connected with this hierarchic context-free system (it is usually not unique). The diagram shows one such tree, which represents the string $aaacbbb$ in the grammar with rules $I\to a'Ib$, $I\to aIb'$, $I\to c$ ($I$ is the initial symbol, while the prime serves as the mark); this tree corresponds to the derivation

$$(I,aIb',aaIb'b',aaa'Ibb'b',aaa'cbb'b'),$$

and the parentheses serve to separate non-trivial components.

Figure: g044800a

The most important partial class of dominating grammars are the so-called simple dominating grammars, in which only terminal symbols appear on the right-hand sides of the rules. Thus, the grammar of the example shown above is simple. For any simple dominating grammar there exists a natural number $k$ such that in each "derivation" tree representing some string in this grammar not more than $k$ arcs issue out of any vertex. Conversely, each dominating grammar with this property has an equivalent simple dominating grammar such that, for any string, the sets of "derivation" trees defined for it by the two grammars are identical.

A simple dominating grammar is also called a dependency grammar.

References

[1]	M.I. Beletskii, "Context-free and domination grammars and the algorithmic problems connected with them" Cybernetics , 3 : 4 (1967) pp. 74–80 Kibernetika (Kiev) , 3 : 4 (1967) pp. 90–97
[2]	A.V. Gladkii, "Formal grammars and languages" , Moscow (1973) (In Russian)

Comments

Dependency grammar is in Eastern Europe the most prominent linguistic theory.

Cf. also Formal languages and automata.

References

[a1]	I. [I.A. Melchuk] Melčuk, "Dependency syntax. Theory and practice" , State Univ. New York Press (1988) (Translated from Russian)