Characterizations of Recursively Enumerable Languages by Programmed Grammars with Unconditional Transfer
Henning Fernau, Frank Stephan · Journal of automata, languages and combinatorics · 1999
We prove that every recursively enumerable language can be generated by a programmed grammar with context-free core rules using unconditional transfer with left-most derivation of type 3 or type 2. Interestingly, we have to give a non-constructive proof of the first mentioned universality result based on Higman's lemma, since finding a transformation from a Turing machine to a programmed grammar with unconditional transfer and leftmost derivation of type 3 turns out to be equivalent to solving the halting problem for Turing machines. As a corollary, we show that every recursively enumerable tally language can be generated by a programmed grammar with context-free core rules using unconditional transfer or by some $k$-limited ET0L system, where $k$ is an arbitrary positive integer.