It is shown to be undecidable whether an epsilon-free finite substitution and a two-state simple epsilon-free ngsm are equivalent on {a,b}*. Consequently, the state-minimization of such ngsm's and the nonterminal-minimization of linear grammars having two nonterminals are undecidable. Applications to some other decision problems concerning epsilon-free finite substitutions and linear grammars are also given. Finally it is shown that the time-equivalence problem is undecidable for propagating OL systems, i.e., for iterated epsilon-free finite substitutions. This solves an open problem presented in [4]. [References: 11]
展开▼
