Introduction to Languages and the Theory of Computation,3E [Special Indian Edition]
John Martin,
North Dakota State University
ISBN: 0070660484 Copyright year: 2007
Preface
This book is an introduction to the theory of computation. It emphasizes
formal languages, models of computation, and computability, and it includes
an introduction to computational complexity and NP-completeness.
Most students studying these topics have already had experience in the practice
of computation. They have used a number of technologies related to computers; now
they can begin to acquire an appreciation of computer science as a coherent discipline.
The ideas are profound—and fun to think about—and the principles will not quickly
become obsolete. Finally, students can gain proficiency with mathematical tools and
formal methods, at the same time that they see how these techniques are applied to
computing.
I believe that the best way to present theoretical topics such as the ones in this
book is to take advantage of the clarity and precision of mathematical language—
provided the presentation is accessible to readers who are still learning to use this
language. The book attempts to introduce the necessary mathematical tools gently
and gradually, in the context in which they are used, and to provide discussion and
examples that make the language intelligible. The first two chapters present the
topics from discrete mathematics that come up later, including a detailed discussion
of mathematical induction. As a result, the text can be read by students without a
strong background in discrete math, and it should also be appropriate for students
whose skills in that area need to be consolidated and sharpened.
The organizational changes in the third edition are not as dramatic as those in the
second. One chapter was broken up and distributed among the remaining fourteen,
and sections of several chapters were reworked and rearranged. In addition to changes
in organization, there were plenty of opportunities throughout to rewrite, to correct
proofs and examples and make them easier to understand, to add examples, and to
replace examples by others that illustrate principles better. Some exercises have
been added, some others have been modified, and the exercises in each chapter have
been grouped into ordinary ones and more challenging ones. In the Turing machine
chapter, I have followed the advice of two reviewers in adopting a more standard and
more intuitive definition of halting.
Whether or not Part I is covered in detail, I recommend covering Section 1.5,
which introduces notation and terminology involving languages. It may also be
desirable to review mathematical induction, particularly the sections on recursive
definitions and structural induction and the examples having to do with formal languages.
At North Dakota State, the text is used in a two-semester sequence required
of undergraduate computer science majors, and there is more than enough material
for both semesters. Aone-semester course omitting most of Part I could cover regular
and context-free languages, and the corresponding automata, and at least some of the
theory of Turing machines and solvability. In addition, since most of Parts IV, V, and
VI are substantially independent of the first three parts, the text can also be used in a
course on Turing machines, computability, and complexity.
I am grateful to the many people who have helped me with all three editions of
this text. Particular thanks are due to Ting-Lu Huang, who pointed out an error in the
proof of Theorem 4.2 in the second edition, and to Jonathan Goldstine, who provided
several corrections to Chapters 7 and 8. I appreciate the thoughtful and detailed comments
of BruceWieand, North Carolina State University; Edward Ashcroft, Arizona
State University; Ding-Zhu Du, University of Minnesota;William D. Shoaff, Florida
Institute of Technology; and Sharon Tuttle, Humboldt State University, who reviewed
the second edition, and Ding-Zhu Du, University of Minnesota; Leonard M. Faltz,
Arizona State University; and Nilfur Onder, Michigan Tech, who reviewed a preliminary
version of this edition. Their help has resulted in a number of improvements,
including the modification in Chapter 9 mentioned earlier. Melinda Dougharty at
McGraw-Hill has been delightful to work with, and I also appreciate the support and
professionalism of Betsy Jones and Peggy Selle. Finally, thanks once again to my
wife Pippa for her help, both tangible and intangible.John C. Martin
2007
Tata McGraw-Hill