Undecidability Results for Uniformly k-Limited 0L Systems
Dietmar Wätjen · Universitätsbibliothek Gießen · 2000
In this paper we shall prove that it is undecidable whether the intersection of two uniformly $k$-limited 0L languages is empty, finite, regular, context-free, a $k$-limited or a uniformly $k$-limited language, whether the language generated by a context-free grammar is a uniformly $k$-limited 0L language or whether a uniformly $k$-limited T0L language can be generated by a context-free grammar. Furthermore, it is undecidable whether the union of two uniformly $k$-limited 0L languages is such a language again.