As for pushdown automata, we consider labelled Turing machines with epsilon-rules. With any Turing machine M and with a rational set C of configurations, we associate the restriction to C of the epsilon-closure of the transition set of M. We get the same family of graphs by using the labelled word rewriting systems. We show that this family is the set of graphs obtained from the binary tree by applying an inverse mapping into F followed by a rational restriction, where F is any family of recursively enumerable languages containing the rational closure of all linear languages. We show also that this family is obtained from the rational-graphs by inverse rational mappings. Finally we show that this family is also the set of graphs recognized by (unlabelled) Turing machines with labelled final states, and even if we restrict to deterministic Turing Machines. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 25]
展开▼
