an introduction to formal languages and automata

Instructors looking for a general reference on automata and formal languages, or a textbook for a mathematically sophisticated audience, should take note that Linz’s book lacks a comprehensive bibliography (the one-page list of references consists primarily of other theory textbooks). More than anything else, the book needs to provide readers with a broader framework that naturally motivates the many topics covered. Perhaps students would be more pleased to learn about the existence of regular expression packages in scripting languages such as Perl and Python, or would appreciate seeing examples of the Unix grep command for file searching. To take just one example, Linz mentions the vi editor as a program that uses regular operators. For students likely to pursue more advanced study in theoretical topics, the presentation is appropriate for students who are more inclined to pursue software development or other applications, the motivation for some topics is lacking. The author identifies the book’s intended audience as sophomore or junior computer science/computer engineering students, with some background in programming, data structures, and discrete mathematics. The presentation is fairly straightforward and readable, especially for what is essentially a mathematics text.

While such an approach tends to be a bit dry, it is fine for instructors who are accustomed to this format, and who can infuse the material with sufficient excitement and enthusiasm. Solutions to some of the exercises appear in the appendix. The presentation is fairly conventional: introduce the new concept, give formal definitions, provide examples, give mathematical justifications (usually complete proofs, although some proofs are omitted or given in outline only), and end with a set of exercises. The latest edition of Linz’s theory textbook follows the same outline as the previous one: it begins with a chapter on mathematical preliminaries moves through the Chomsky hierarchy (regular, context-free, and recursively enumerable languages, with a brief mention of context-sensitive languages) and concludes with one chapter each on the topics of undecidability, alternate models of computation, and complexity classes.

An introduction to formal languages and automata