T
Preface
his book is designed for an introductory course on formal languages,
automata, computability, and related matters. These topics form a
major part of what is known as the theory of computation. A course on
this subject matter is now standard in the computer science curriculum
and is often taught fairly early in the program. Hence, the prospective
audience for this bookconsists primarily of sophomores and juniors majoring in
computer science or computer engineering.
Prerequisites for the material in this bookare a knowledge of some higherlevel programming language (commonly C, C++, or Java™) and familiarity with
the fundamentals of data structures and algorithms. A course in discrete
mathematics that includes set theory, functions, relations, logic, and elements of
mathematical reasoning is essential. Such a course is part of the standard
introductory computer science curriculum.
The study of the theory of computation has several purposes, most
importantly (1) to familiarize students with the foundations and principles of
computer science, (2) to teach material that is useful in subsequent courses, and
(3) to strengthen students’ ability to carry out formal and rigorous mathematical
arguments. The presentation I have chosen for this text favors the first two
purposes, although I would argue that it also serves the third. To present ideas
clearly and to give students insight into the material, the text stresses intuitive
motivation and illustration of ideas through examples. When there is a choice, I
prefer arguments that are easily grasped to those that are concise and elegant but
difficult in concept. I state definitions and theorems precisely and give the
motivation for proofs, but often leave out the routine and tedious details. I
believe that this is desirable for pedagogical reasons. Many proofs are unexciting
applications of induction or contradiction with differences that are specific to
particular problems. Presenting such arguments in full detail is not only
unnecessary, but interferes with the flow of the story. Therefore, quite a few of
the proofs are brief and someone who insists on completeness may consider
them lacking in detail. I do not see this as a drawback. Mathematical skills are
not the byproduct of reading someone else's arguments, but come from thinking
about the essence of a problem, discovering ideas suitable to make the point,
Preface
his book is designed for an introductory course on formal languages,
automata, computability, and related matters. These topics form a
major part of what is known as the theory of computation. A course on
this subject matter is now standard in the computer science curriculum
and is often taught fairly early in the program. Hence, the prospective
audience for this bookconsists primarily of sophomores and juniors majoring in
computer science or computer engineering.
Prerequisites for the material in this bookare a knowledge of some higherlevel programming language (commonly C, C++, or Java™) and familiarity with
the fundamentals of data structures and algorithms. A course in discrete
mathematics that includes set theory, functions, relations, logic, and elements of
mathematical reasoning is essential. Such a course is part of the standard
introductory computer science curriculum.
The study of the theory of computation has several purposes, most
importantly (1) to familiarize students with the foundations and principles of
computer science, (2) to teach material that is useful in subsequent courses, and
(3) to strengthen students’ ability to carry out formal and rigorous mathematical
arguments. The presentation I have chosen for this text favors the first two
purposes, although I would argue that it also serves the third. To present ideas
clearly and to give students insight into the material, the text stresses intuitive
motivation and illustration of ideas through examples. When there is a choice, I
prefer arguments that are easily grasped to those that are concise and elegant but
difficult in concept. I state definitions and theorems precisely and give the
motivation for proofs, but often leave out the routine and tedious details. I
believe that this is desirable for pedagogical reasons. Many proofs are unexciting
applications of induction or contradiction with differences that are specific to
particular problems. Presenting such arguments in full detail is not only
unnecessary, but interferes with the flow of the story. Therefore, quite a few of
the proofs are brief and someone who insists on completeness may consider
them lacking in detail. I do not see this as a drawback. Mathematical skills are
not the byproduct of reading someone else's arguments, but come from thinking
about the essence of a problem, discovering ideas suitable to make the point,