The Chomsky hierarchy, which is the stuff of classical computer science (CS) theory at the advanced undergraduate and beginning graduate levels, classifies formal grammars (and their associated formal languages) into four types: regular (type 3), context-free (type 2), context-sensitive (type 1), and recursively enumerable (type 0, or unrestricted). The regular grammars are familiar to us through regular expression syntax (for example, in Unix shell scripts), and their languages are accepted by finite state automata. The context-free grammars (CFGs) are commonly known as the bases for most programming languages, and their languages are accepted by pushdown automata. Context-sensitive grammars (CSGs) seem to relate more than CFGs to grammars for natural languages, and their languages are accepted by linear bounded automata. Recursively enumerable languages are generated by unrestricted grammars and are accepted by Turing machines.

There is a vast literature concerning CFGs, which have sufficient richness to capture many interesting properties, while also being amenable to thorough analyses without having too many convoluted questions that would have researchers running in circles or into dead ends that absolutely stop all progress. CSGs, on the other hand, are even more rich than CFGs and hence more alluring targets for scholarly interest, but working on them is considerably more difficult, and many important questions about them are difficult to solve, or else remain unsolved (for instance, membership in a context-free language is determinable in polynomial time, while the problem of determining membership in a context-sensitive language is known to be PSPACE-complete).

Thus, for the past few decades, there have been many efforts made to discover special versions of CFGs that retain the simplicity of use of classical CFGs, while also adding some of the power that CSGs have that classical CFGs do not. One important direction that has been attempted is in the so-called regulated CFGs, which the authors call regulated grammars; an orderly and concise discussion of these is the purpose of the present book. The regulated grammars are “based upon CFGs extended by additional regulating mechanisms by which they control the way language generation is performed” (p. 4). As the authors admit, too much is known about regulated grammars for proper coverage in a single book, so to permit orderly discussion, they confine themselves to discussing context-based regulation and rule-based regulation, which are two primary types of regulating mechanisms commonly added to CFGs.

The book consists of 22 chapters divided among nine parts. Part 1, consisting of three chapters, gives a broad introduction and features some of the relevant basics of mathematics and computation theory. The two chapters in Part 2 examine context-based grammatical regulation and rule-based grammatical regulation, respectively. Part 3 explores special topics (that is, various theoretical results) concerning regulated grammars in four chapters. Parts 4 and 5 cover parallelism in regulated grammars and on regulated grammar systems, respectively.

There are two chapters each in Parts 6 and 7; they deal with results concerning automata for regulated languages. In Part 8, two chapters, the authors explore applications of regulated grammars in application domains (linguistics, biology, and compiler design). Part 9 concludes over two chapters, also giving insights and hints for future work.

The book is well written and produced, and should be warmly received by its community. Each chapter is accompanied by a bibliography, and the authors suggest many open problems that should be welcomed by researchers, especially graduate students just embarking on research. Due to the advanced nature of its material and the lack of instructor resources, this book is probably less suitable as a text for a regular classroom course, though selected chapters can surely be judiciously added to the list of instructor-suggested readings in advanced courses on formal languages and automata theory, or used by instructors themselves to prepare material for classroom teaching.