FORMAL LANGUAGES AND GROUP THEORY

摘要

1 Introduction Our aim is to explore some connections between word problems of groups and formal language theory. One question is whether any finitely presented group has a recursive word problem, i.e., if there is an algorithm to decide if a given word in the generators of such a group represents the identity; this was shown not to be the case by Novikov and Boone independently [37, 6]. A finitely presented group has a recursively enumerable word problem however, i.e., there is a process listing the words representing the identity; the process will not terminate (there are infinitely many such words) but any word representing the identity will eventually appear.