Jumping Computation

Chapter 5Sequential Jumping Grammars

This three-section chapter is organized as follows. Section 5.1 gives an introduction into its subject. Section 5.2 recalls all the definitions that are needed and illustrates them by examples. Then, Section 5.3 presents fundamental results as well as open problems concerning jumping grammars.

5.1 Introduction

To start with, recall the notion of a classical grammar (see Section 2.3), G, which represents a language-generating rewriting system based upon an alphabet of symbols and a finite set of production rules or, simply, rules. The alphabet of symbols is divided into two disjoint subalphabets—the alphabet of terminal symbols and the alphabet of nonterminal symbols. Each production rule represents a pair ...