The Sequence Equivalence Problem is Decidable for 0S Systems
Andrzej Ehrenfeucht, G. S. Rozenberg · Journal of the ACM · 1980
0S systems generalize context-free grammars without nontermmals it is shown that it is decidable whether or not two arbitrary 0S systems generate the same set of (derivation) sequences It is obtained as a corollary that it is decidable whether or not two arbitrary context-free grammars have the same sets of derivation sequences KEY WORDS AND PHRASES formal languages, context-free grammars, 0S systems, decision problems cg CATEOOgmS 5 23 IntroductionWhen considering a context-free grammar G = (VN, VT, P, S) from the "computational point of view," one can restrict oneself to G = (VN O VT, P, S), which is "a context-free grammar wRhout nontermmals"; such systems have been investigated, e.g., in [l] and [4].When generalized somewhat, such systems give rise to 0S systems, which can be viewed as the _sequential counterpart of 0L systems (see, e.g., [3]).Studying 0S systems is, m our opinion, a very natural step m a systematic study of the foundations of formal language theory.On the one hand, one hopes m this way to build up a more thorough foundation for the theory of context-free languages; on the other hand, when contrasted with the theory of 0L systems, such a study can shed new light on the basic differences between parallel and sequential rewriting systems.In this paper we view a 0S system as a system for generating sequences of words (all "derivations" in it), and then we consider the basic decision problem: Do two arbitrary 0S :~ "~,~ms generate the same set of sequences?We prove that this problem is decidable and show that as a corollary it yields the following result: It is decidable whether or not two arbitrary context-free grammars generate the same set of derivation sequences. PreliminariesWe assume that the reader is familiar with basics of the theory of context-free grammars