This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

This paper introduces and studies jumping pure grammars, which are conceptualized just like classical pure grammars except that during the applications of their productions, they can jump over symbols in either direction within the rewritten strings. The paper compares the generative power of jumping pure grammars with that of classical pure grammars while distinguishing between their versions with and without erasing productions. Apart from sequential versions, the paper makes an analogical study in terms of parallel versions of jumping pure grammars represented by 0L grammars.

Conceptually, jumping scattered context grammars coincide with their standard counterparts, but they work differently. Indeed, a jumping version can apply a rule of the form ( A 1 , A 2 , . . . , A n ) → ( x 1 , x 2 , . . . , x n ) so it simultaneously erases A 1 , A 2 , . . . , A n in the current sentential form while inserting x 1 , x 2 , . . . , x n possibly at different positions than the erased nonterminals. In fact, this paper introduces and studies scattered context grammars working under nine different jumping derivation modes, all of which give rise to the computational completeness. Indeed, the paper characterize the family of recursively enumerable languages by scattered context grammars working under any of these jumping modes. In its conclusion, the paper sketches application perspectives and formulates several open problems.

This paper establishes two new normal forms for phrase-structure grammars in which both context-free rules and non-context-free rules are in prescribed forms. In addition, a limit is placed on the number of context-free rules. More specifically, the first form has | $2 + n$ | context-free rules, where | $n$ | is the number of terminals. Concerning non-context-free rules, each of them has the form | $AB \rightarrow CD$ | , where | $A, B, C, D$ | are nonterminals. The second normal form has always only two context-free rules— | $S \to S\#$ | and | $\# \to \varepsilon $ | , where | $S$ | is the start symbol, | $\#$ | is a nonterminal, and | $ \varepsilon $ | is the empty string. Regarding non-context-free rules, each of them is of the form | $AB \rightarrow XD$ | , where | $A, B, D$ | are nonterminals and | $X$ | is a nonterminal or a terminal.

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.