On some classes of contextual grammars

In this paper, we introduce some new variants of contextual grammars and investigate their generative power. We consider a restricted version of depth-first contextual grammars, which depends on length of the inserting contexts. Using this variant, we give a solution to the open problem P14 listed in [8]. We also introduce random context contextual grammars and compare its generative power with the families IC, ICC, EC, ECC, TC. Time-varying contextual grammars are introduced which resemble time-varying grammars. We compare the generative power of this variant with the families of internal, external, total, matrix, and programmed contextual grammars.