Discontinuous-constituent phrase structure grammar

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Discontinuous-constituent phrase structure grammar" – news · newspapers · books · scholar · JSTOR (August 2021)

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). 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.

Description

Rewrite 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 $X\to \alpha$ where $\alpha$ 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 $X\to \alpha$ , an occurrence of $X$ may be rewritten as $\alpha$ .

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

{\ce {S->VP\ NP_{subj}}}

{\ce {VP->ITV~|~TV\ \_\ NP_{obj}}}

{\ce {NP->{\it {{John}~|~{\it {{Susan}~|~...}}}}}}

{\ce {ITV->{\it {{ran}~|~{\it {{danced}~|~...}}}}}}

{\ce {TV->{\it {{saw}~|~{\it {{met}~|~...}}}}}}

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:

{\ce {S->VP\ NP_{subj}->TV\ NP_{subj}NP_{obj}->{\mathit {saw}}\ NP_{subj}\ NP_{obj}->{\mathit {saw}}\ {\mathit {John}}\ NP_{obj}->{\mathit {saw}}\ {\mathit {John}}\ {\mathit {Mary}}}}

References

Harman, Gilbert H. 1963. Generative Grammars without Transformation Rules: A Defense of Phrase Structure. Language 39(4), 597-616.

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Abstract machines
Type-0 — Type-1 — — — — — Type-2 — — Type-3 — —	Unrestricted (no common name) Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting systems Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular — Non-recursive	Recursively enumerable Decidable Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting language Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular Star-free Finite	Turing machine Decider Linear-bounded PTIME Turing Machine Nested stack Thread automaton restricted Tree stack automaton Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free (with aperiodic finite monoid) Acyclic finite

Each category of languages, except those marked by a , is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

Categories: