Sequential Machines and Automata Theory

Quite frequently, a subject of considerable academic interest will emerge with a flow of textbooks that range from very narrow to very broad in scope. Not quite so frequently, a well-organized and comprehensive textbook is written-Booth has written such a book. Chapter I is a brief introduction to the terminology, notation, and types of problems in sequential machines and automata theory. Although the state-variable notation is useful, it is also rather cumbersome since both subscripts and superscripts (with parentheses) are required in each writing of a single state-variable. The fundamental concepts of modern algebra are summarized in Chapter II. This chapter includes such topics as sets, operations on elements, mathematical systems, semigroups, groups, rings, finite fields, isomorphisms, and homomorphisms. An appropriate introduction to sequential machines is given in Chapter III. In the opinion of this reviewer, this chapter should contain a good treatment of the state assignment problem to accomplish both a thorough presentation of sequential machines and a timely preparation for the decomposition of sequential machines presented in Chapter IV. An average reader should find that the types of decomposition are presented quite clearly, even though the mechanics necessary to accomplish the decomposition of a given machine are rather obscure. A discussion of "self-dependent" and "cross-dependent" sets of functions would help to prepare the reader for "loop-free" and "feedback" representations of composite machines. Chapter V is a thorough coverage of the control and identification of sequential machines. Particular attention is given to terminal-state and initial-state identification problems. In Chapter VI, the author considers the problem of machine specification through the use of regular expressions. He states that his goal is to develop a method to generate a state table for a sequential machine from a description of the machine's required external characteristics. His presentation bears him out; he does not delve very deeply into any theory or any uses of regular expressions unless the topic leads toward the formation of a state table. In particular, he avoids the use of nondeterministic machine models which often appear in the literature. The state-table representation of a sequential machine is desired because this is the type of machine specification from which machine behavior is analyzed in previous chapters.