Namespaces
Variants
Actions

Difference between revisions of "Grammar, dominating"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
A type of formal grammar (cf. [[Grammar, formal|Grammar, formal]]) serving to generate strings together with derivation trees (cf. [[Syntactic structure|Syntactic structure]]). Formally, a dominating grammar can be defined as a context-free grammar (cf. [[Grammar, context-free|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448001.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448002.png" /> is the initial symbol and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448003.png" /> 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448004.png" /> in the grammar with rules <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448005.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448006.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448007.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448008.png" /> is the initial symbol, while the prime serves as the mark); this tree corresponds to the derivation
+
{{TEX|done}}
 +
A type of formal grammar (cf. [[Grammar, formal|Grammar, formal]]) serving to generate strings together with derivation trees (cf. [[Syntactic structure|Syntactic structure]]). Formally, a dominating grammar can be defined as a context-free grammar (cf. [[Grammar, context-free|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|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g0448009.png" /></td> </tr></table>
+
$$(I,aIb',aaIb'b',aaa'Ibb'b',aaa'cbb'b'),$$
  
 
and the parentheses serve to separate non-trivial components.
 
and the parentheses serve to separate non-trivial components.
Line 9: Line 10:
 
Figure: g044800a
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g04480010.png" /> such that in each "derivation" tree representing some string in this grammar not more than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044800/g04480011.png" /> 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.
+
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.
 
A simple dominating grammar is also called a dependency grammar.

Latest revision as of 17:18, 3 November 2014

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)
How to Cite This Entry:
Grammar, dominating. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Grammar,_dominating&oldid=18932
This article was adapted from an original article by A.V. Gladkii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article