The decidability of a mapping problem for generalized sequential machines with final states

摘要

The following problem is shown to be decidable for arbitrary regular sets R1 and R2: Does there exist a generalized sequential machine with final states which maps R1 onto R2? In the development of the solution a graphical interpretation of bounded and unbounded regular sets is presented. Also, the subproblem when R1 and R2 are arbitrary bounded regular sets is shown to be decidable.