Friendship paradox

2014-01-22T04:04:10Z

172.248.1.111: /* Applications */

{{underlinked|date=October 2012}}
{{Orphan|date=December 2010}}

'''Discontinuous-constituent Phrase Structure Grammar''' (DCPSG) (distinct from Discontinuous Phrase Structure Grammar/DPSG) is a formalism for describing discontinuous phrase structures in natural language, such as verb phrases in VSO languages. The formalism was introduced in the slightly more constrained form of Discontinuous-constituent Phrase Structure Grammar with Subscripts and Deletes (DCPSGsd) in Harman (1963).<ref name="harman1963">Harman, Gilbert H. 1963. Generative Grammars without Transformation Rules: A Defense of Phrase Structure. ''Language'' 39(4), 597-616.</ref> DCPSGs describe a superset of the context-free languages, by means of rewrite rules that permit a limited amount of wrapping, similar to that found in [[Head grammar]].
{{tocright}}

==Description==

Re''write rules of a '''DCPSG''' are identical to those of a CFG, with the addition of a meta-symbol, denoted here as an underscore. ''DCPSG'' rules therefore have the general form <math>X \to \alpha</math> where <math>\alpha</math> is a string of terminal symbols and/or non-terminal symbols and at most one underscore.

The rewrite semantics of DCPSG are identical as those of a CFG when the rule being used does not contain an underscore: given a rule <math>X \to \alpha</math>, an occurrence of <math>X</math> may be rewritten as <math>\alpha</math>.

For rules with an underscore, the rewrite semantics are slightly different: given a rule <math>X \to \alpha \_ \beta</math>, an occurrence of <math>X</math> can be rewritten as <math>\alpha</math>, with <math>\beta</math> being inserted immediately after the next non-terminal that is introduced at the same time. Using strict left-most productions, <math>\beta</math> is simply inserted immediately after the non-terminal that follows <math>X</math> prior to the rewrite.
''

==Example==

We can characterize the gross sentence structure of a VSO language such as Irish with the following rules (substituting English words for Irish words, and using subscripts solely for demonstration of discontinuity):

<math>S \to VP\ NP_{subj}</math>

<math>VP \to ITV ~|~ TV \ \_ \ NP_{obj}</math>

<math>NP \to John ~|~ Susan ~|~ ...</math>

<math>ITV \to ran ~|~ danced ~|~ ...</math>

<math>TV \to saw ~|~ met ~|~ ...</math>

A derivation for the sentence ''saw John Susan'', where ''John'' is the subject, and ''Susan'' is the direct object forming a VP with ''saw'' is:

<math>S \to VP\ NP_{subj} \to TV\ NP_{subj} NP_{obj} \to saw\ NP_{subj}\ NP_{obj} \to saw\ John\ NP_{obj} \to saw\ John\ Mary</math>

==References==

<references/>

{{Formal languages and grammars}}

{{DEFAULTSORT:Discontinuous-Constituent Phrase Structure Grammar}}
[[Category:Formal languages]]
[[Category:Grammar frameworks]]

formulasearchengine - User contributions [en]

Friendship paradox