abstract models of computers and computation. These models embody the
important features that are common to both hardware and software and that are
essential to many of the special and complex constructs we encounter while
working with computers. Even when such models are too simple to be applicable
immediately to real-world situations, the insights we gain from studying them
provide the foundation on which specific development is based. This approach
is, of course, not unique to computer science. The construction of models is one
of the essentials of any scientific discipline, and the usefulness of a discipline is
often dependent on the existence of simple, yet powerful, theories and laws.
A second, and perhaps not so obvious, answer is that the ideas we will
discuss have some immediate and important applications. The fields of digital
design, programming languages, and compilers are the most obvious examples,
but there are many others. The concepts we study here run like a thread through
much of computer science, from operating systems to pattern recognition.
The third answer is one of which we hope to convince the reader. The subject
matteris intellectually stimulating and fun. It provides many challenging, puzzlelike problems that can lead to some sleepless nights. This is problem solving in
its pure essence.
In this book, we will look at models that represent features at the core of all
computers and their applications. To model the hardware of a computer, we
introduce the notion of an automaton (plural, automata). An automaton is a
construct that possesses all the indispensable features of a digital computer. It
accepts input, produces output, may have some temporary storage, and can make
decisions in transforming the input into the output. A formal language is an
abstraction of the general characteristics of programming languages. A formal
language consists of a set of symbols and some rules of formation by which
these symbols can be combined into entities called sentences. A formal language
is the set of all sentences permitted by the rules of formation. Although some of
the formal languages we study here are simpler than programming languages,
they have many of the same essential features. We can learn a great deal about
programming languages from formal languages. Finally, we will formalize the
concept of a mechanical computation by giving a precise definition of the term
algorithm and study the kinds of problems that are (and are not) suitable for
solution by such mechanical means. In the course of our study, we will show the
close connection between these abstractions and investigate the conclusions we
can derive from them.
In the first chapter, we look at these basic ideas in a very broad way to set the
stage for later work. In Section 1.1, we review the main ideas from mathematics
important features that are common to both hardware and software and that are
essential to many of the special and complex constructs we encounter while
working with computers. Even when such models are too simple to be applicable
immediately to real-world situations, the insights we gain from studying them
provide the foundation on which specific development is based. This approach
is, of course, not unique to computer science. The construction of models is one
of the essentials of any scientific discipline, and the usefulness of a discipline is
often dependent on the existence of simple, yet powerful, theories and laws.
A second, and perhaps not so obvious, answer is that the ideas we will
discuss have some immediate and important applications. The fields of digital
design, programming languages, and compilers are the most obvious examples,
but there are many others. The concepts we study here run like a thread through
much of computer science, from operating systems to pattern recognition.
The third answer is one of which we hope to convince the reader. The subject
matteris intellectually stimulating and fun. It provides many challenging, puzzlelike problems that can lead to some sleepless nights. This is problem solving in
its pure essence.
In this book, we will look at models that represent features at the core of all
computers and their applications. To model the hardware of a computer, we
introduce the notion of an automaton (plural, automata). An automaton is a
construct that possesses all the indispensable features of a digital computer. It
accepts input, produces output, may have some temporary storage, and can make
decisions in transforming the input into the output. A formal language is an
abstraction of the general characteristics of programming languages. A formal
language consists of a set of symbols and some rules of formation by which
these symbols can be combined into entities called sentences. A formal language
is the set of all sentences permitted by the rules of formation. Although some of
the formal languages we study here are simpler than programming languages,
they have many of the same essential features. We can learn a great deal about
programming languages from formal languages. Finally, we will formalize the
concept of a mechanical computation by giving a precise definition of the term
algorithm and study the kinds of problems that are (and are not) suitable for
solution by such mechanical means. In the course of our study, we will show the
close connection between these abstractions and investigate the conclusions we
can derive from them.
In the first chapter, we look at these basic ideas in a very broad way to set the
stage for later work. In Section 1.1, we review the main ideas from mathematics