Contextual grammars were introduced by S. Marcus in 1969 with a deep linguistic motivation. In contrast to the standard rewriting grammars, these grammars generate languages by adjoining contexts in each sentencial form, according to a selector present in the string and the grammars have no distinction between terminal and nonterminal.
In this book, the author presented a few results which are of interest to the domain of mildly context sensitive (MCS) formalisms. With this aim, the author discussed two new classes of contextual grammars, namely end-marked maximal depth-first (emdf) and inner end-marked maximal depth-first (iemdf) contextual grammars and raise arguments for the grammars can be considered as generative models for natural languages.
These variants are obtained by imposing special conditions in selectors and contexts of maximal depth-first grammars. The author proved that the three basic non-context-free constructions in natural languages can be realized upon using these variants with regular
selectors, and the membership problem for these families of languages is decidable in polynomial time. The family of languages generated by iemdf grammars with regular selectors contains semilinear languages only, but however, the family of languages generated by emdf grammars with regular selectors contains non-semilinear languages also. The author also solved the semilinear issue for the family of languages generated by maximal depth-first (mdf), maximal lengthwise depth-first (mldf) and maximal local (mloc) contextual grammars. Consequently, the author saw that the family of languages generated by iemdf grammars possess the MCS formalism. Further, they show that any recursive enumerable language can be obtained from the languages generated
by emdf,mdf and mldf grammars with regular selectors by taking appropriate morphisms, weak coding and left quotient.