Further Reading (Formal Languages and Computation)

Formal Languages and Computation by Meduna is designed strictly for undergraduate students. All topics under discussion are motivated by giving examples of how they are related to applications. As far as the theory is concerned, the book first presents all theoretical results informally and sketches their proofs intuitively; then, step by step, it gently leads the reader to formal versions of these proofs. Many applications are included in order to see how theory and practice work together. After reading this book, the students will feel at ease with more complicated books, including the textbooks referenced in the next list.

The list references six theoretically oriented books, which are strongly recommended as a further reading. Their main features, differences, strengths, and weaknesses are sketched next, too. Apart from them, this list includes a reference to a textbook about applications of formal language theory in compiler design to promote respect for its “real-world” use in practice.

This famous book is a revised and updated version of its 1979 version, whose predecessor was published in 1969 under the title “Formal Languages and Their Relation to Automata.” It covers all the major topics in the theory of formal languages, automata, and computation. This text is a splendid reference for research in these areas. It is primarily a textbook for postgraduate students in theoretical computer science. This book contains no applications, however.

This book contains all the material needed for an advanced course on theory of computation and complexity. Sipser is a talented writer, and thanks to his writing style, it nicely presents all the knowledge concerning this theory in an effective way. Proofs on theorems are given almost always in the following two-phase way: first, the book gives the idea that lies behind the proof, and second, it gives the proof itself in a rigorous way. Regarding formal languages and their models, the book restricts its attention to the models needed in the theory of computation. Just like Hopcroft, Motwani, and Ullman, Sipser completely ignores applications. This book represents a good textbook for graduate and postgraduate students.

This book provides a very good introduction to the theory of automata and computability. It contains a reasonable selection of essential material concerning the theory of formal languages, automata, and computation. The presentation is somewhat unusual because it consists of lectures rather than chapters. Apart from the basic lectures, the text adds eleven supplementary lectures that cover special and advanced topics on the subject. Frequently, Kozen makes seemingly difficult-to-understand topics easy-to-grasp.

This book is a mathematically oriented survey of some important fundamental concepts in the theory of languages and computation, which covers a wider range of topics than most other introductory books on the subject. It contains worked out proofs of every major theorem, but the reader needs a fairly high level of mathematical sophistication to fully understand these proofs. It is strictly theoretically oriented. As a result, it is not designed for undergraduate students. Although it contains some algorithms and examples, their presentation is theoretical, too.

This textbook provides the reader with a mathematically sound presentation of the theory of formal languages and computation at a level corresponding to senior level computer science majors. The theoretical concepts are presented so they are preceded by an intuitive understanding of the concepts through numerous examples and illustrations. It contains a good selection of topics concerning computational complexity. It provides a flexible format giving professors the ability to design their courses that concentrate on specific areas within automata theory, computability, or computational complexity. Parsing based upon LL and LR grammars is included to provide the groundwork for the study of compiler design, but its presentation is so theoretical that undergraduate students cannot see how to implement parsers based upon these grammars. All in all, the text is far beyond the undergraduate level.

This textbook presents a step-by-step development of the theory of automata, languages and computation. The text is organized in such a way that it allows the design of various courses based on selected material. Areas featured in the book include formal-language-defining models, computability, decidability, and computational complexity. The text also discusses modern trends in the theory of automata and formal languages. It also explains the design of programming languages and their compilers. As a matter of fact, it includes the construction of a complete compiler. The text uses clear definitions, easy-to-follow proofs and helpful examples to make formerly obscure concepts easy to understand. It has many challenging exercises and programming projects to enhance the reader's comprehension. In order to put the theory firmly into a 'real world' context, it contains lots of realistic illustrations and applications in practical computer science. It is primarily a textbook for postgraduate students in theoretical computer science, however.

Maintaining a balance between a theoretical and practical approach to compilers, this book serves as an introduction to compiler writing for undergraduate students. Based on automata and grammars, it explains the concepts, methods, and techniques employed in compiler design in a clear and easy-to-follow way. The book describes how compilation techniques are implemented. In fact, throughout the text, a case study illustrates the design of a new programming language and the construction of its compiler. While discussing various compilation techniques, the text demonstrates their implementation through this case study. In addition, the book presents many detailed examples and computer programs to emphasize the applications of the compiler algorithms.

After reading Formal Languages and Computation by Meduna, students might want to study his Elements of Compiler Design to see how to use automata and grammars in compiler design, which represents a quite realistic application area in practical computer science.