ABSTRACT
The fundamental purpose of this chapter is to give an essential body of rigorous knowledge concerning jumping grammars. Since the determination of the power of language-defining devices has always fulfilled perhaps the most important role in formal language theory, it focuses its coverage on this topic. Regarding the general versions of jumping grammars, it demonstrates that they are as powerful as the classical unrestricted grammars. As there exist many important special versions of the unrestricted grammars, the chapter discusses their jumping counterparts as well. It studies the jumping versions of context-free grammars and their special cases, including regular grammars, right-linear grammars, linear grammars, and context-free grammars of finite index. Surprisingly, all of them have a different power than their classical counterparts. The chapter also compares the generative power of jumping grammars with the accepting power of jumping finite automata. More specifically, it demonstrates that regular jumping grammars are as powerful as these automata.
