ABSTRACT

This chapter studies jumping computation based upon the notion of a pure grammar G. It gives an introduction into its subject. The chapter recalls all the terminology needed in this chapter and introduces a variety of jumping pure grammars, illustrated by an example. It presents fundamental results and concludes by summing up ten open problems. Jumping versions of language-defining rewriting systems, such as grammars and automata, represent a brand new trend in formal language theory. In essence, they act just like classical rewriting systems except that they work on strings discontinuously. That is, they apply a production rule so they erase an occurrence of its left-hand side in the rewritten string while placing the right-hand side anywhere in the string, so the position of the insertion may occur far away from the position of the erasure.