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.

Keywords:

• Contextual Grammars
• Depth First
• Time-varying
• Recursively Enumerable Language