Membership for 1-Limited ET0L Languages Is Not Decidable

Joseph went to register with Mary, who was promised in marriage to him. Abstract: In this paper, we show how to encode arbitrary enumerable set of numbers given by register machines within limited EPT0L systems and programmed grammars with unconditional transfer. This result has various consequences, e.g. the existence of nonre-cursive sets generable by 1lET0L systems or by programmed grammars with unconditional transfer. Moreover, ordered grammars are strictly less powerful than 1lET0L systems.