The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications

Abstract

It is shown that the equivalence problem is unsolvable for $\varepsilon $-free nondeterministic generalized sequential machines whose input/output are restricted to unary/binary (binary/unary) alphabets. This strengthens a known result of Griffiths. Applications to some decision problems concerning right-linear grammars and directed graphs are also given.