View source for 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 [[#References|[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 [[#References|[a5]]], turned out to be more useful.

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103701.png" /> be a family of languages. An internal contextual grammar with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103702.png" />-selection is a system

<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/c/c110/c110370/c1103703.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103704.png" /> is an alphabet, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103705.png" /> is a finite language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103706.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103707.png" /> are languages (over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103708.png" />) in the family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c1103709.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037010.png" /> are finite sets of contexts over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037011.png" />, i.e., pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037014.png" />. The elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037015.png" /> are axioms, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037016.png" /> are the selectors of the productions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037018.png" />. With respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037019.png" />, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037020.png" /> one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037021.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037023.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037025.png" />, for certain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037027.png" />. (The contexts in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037028.png" /> can be adjoined to strings in the associated selector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037029.png" />.)

Denoting by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037030.png" /> the reflexive and transitive closure of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037031.png" />, the language generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037032.png" /> can be defined by

<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/c/c110/c110370/c11037033.png" /></td> </tr></table>

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037035.png" /> be the family of languages generated by internal contextual grammars with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037036.png" />-selection. Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037037.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037040.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037042.png" /> 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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037043.png" />;

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037045.png" />;

3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037046.png" /> contains non-semi-linear languages;

4) all families <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037048.png" /> as above, are anti-AFL (cf. [[Trio|Trio]]; [[Abstract family of languages|Abstract family of languages]]);

5) every recursively enumerable language <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037049.png" /> can be written in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037050.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037052.png" /> is a weak coding and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c110/c110370/c11037053.png" /> 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 [[#References|[a1]]], [[#References|[a3]]], [[#References|[a4]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Ehrenfeucht,   Gh. Păun,   G. Rozenberg,   "Contextual grammars"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Handbook of Formal Languages'' , Springer  (1996)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S. Marcus,   "Contextual grammars"  ''Rev. Roum. Math. Pures Appl.'' , '''14'''  (1969)  pp. 1525–1534</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  Gh. Păun,   "Contextual grammars" , Publ. House of the Romanian Acad., Bucharest  (1982)  (In Rumanian)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  Gh. Păun,   "Marcus contextual grammars. After 25 years"  ''Bull. EATCS'' , '''52'''  (1994)  pp. 263–273</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  Gh. Păun,   X.M. Nguyen,   "On the inner contextual grammars"  ''Rev. Roum. Math. Pures Appl.'' , '''25'''  (1980)  pp. 641–651</TD></TR></table>