Contextual grammar

A language-generating device based on the operation of adjoining contexts to strings, according to a selection procedure. Such grammars were introduced (in the external variant, with the contexts adjoined at the ends of the currently generated string) in [a2], with the explicit purpose of obtaining an intrinsic generative mechanism, without auxiliary symbols (as in Chomsky grammars) and making use of the string-context interplay which is fundamental in all linguistic theories. For modelling natural language-syntactical constructions, the internal contextual grammars, introduced in [a5], turned out to be more useful.

Let be a family of languages. An internal contextual grammar with -selection is a system

where is an alphabet, is a finite language over , are languages (over ) in the family , and are finite sets of contexts over , i.e., pairs , , . The elements of are axioms, are the selectors of the productions , . With respect to , for one writes if and only if , , with , , for certain , . (The contexts in can be adjoined to strings in the associated selector .)

Denoting by the reflexive and transitive closure of , the language generated by can be defined by

Let be the family of languages generated by internal contextual grammars with -selection. Denote by , , , , , the families of finite, regular, context-free, context-sensitive, recursively enumerable, and arbitrary languages, respectively. Some basic results for contextual grammars are as follows:

1) ;

2) , ;

3) contains non-semi-linear languages;

4) all families , as above, are anti-AFL (cf. Trio; Abstract family of languages);

5) every recursively enumerable language can be written in the form , where , is a weak coding and is a morphism.

A lot of variants have been considered (left-most, prefix, parallel, blocked derivation, maximal or minimal use of selectors, one-sided contexts, deterministic grammars, etc.). Details can be found in [a1], [a3], [a4].

References[edit]