The pre-NTS property is undecidable for context-free grammars (Q1208437)

A grammar \(G\) is called non-terminal separable (NTS) (respectively, pre- NTS) if the set of sentential forms (respectively, the language) it generates is unchanged when the rules in \(G\) are used both ways. Such grammars were introduced by \textit{L. Boasson} and \textit{G. Senizergues} in [J. Comput. Syst. Sci., 31, 332-342 (1985; Zbl 0604.68087)]. The NTS property is decidable [\textit{F. Otto}, J. Comput. Syst. Sci. 35, 285-310 (1987; Zbl 0645.03033) and \textit{G. Senizergues}, J. Comput. Syst. Sci., 31, 303-331 (1985; Zbl 0604.68086)] in polynomial time [\textit{K. Madlener}, \textit{P. Narandran}, \textit{F. Otto} and \textit{L. Zhang}, Theoret. Comput. Sci. (1993)]. In the present note one proves that the pre-NTS property is undecidable. The use technique is the simulation of a Turing machine through a finite monadic string-rewriting system.