A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

Original languageEnglish
Pages (from-to)341-351
Number of pages11
JournalFundamenta Informaticae
Volume64
Issue number1-4
StatePublished - 7 Sep 2005
Externally publishedYes

    Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software
  • Applied Mathematics
  • Safety, Risk, Reliability and Quality

    Research areas

  • Context-free language, Contextual grammar, Regular language, Trajectory

ID: 41144246