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 language | English |
---|---|
Pages (from-to) | 341-351 |
Number of pages | 11 |
Journal | Fundamenta Informaticae |
Volume | 64 |
Issue number | 1-4 |
State | Published - 7 Sep 2005 |
Externally published | Yes |
ID: 41144246