**INTRODUCTION TO THE THEORY OF COMPUTATION**

This chapter prepares you for what is to come. In Section 1.1, we review some of the main ideas from finite mathematics and establish the notation used in the text. Particularly important are the proof techniques, especially proof by induction and proof by contradiction.

Section 1.2 gives you a first look at the ideas that are at the core of the book: automata, languages, grammars, their definitions, and their relations. In subsequent chapters, we will expand these ideas and study a number of different types of automata and grammars.

In Section 1.3, we encounter some simple examples of the role these concepts play in computer science, particularly in programming languages, digital ...

Start Free Trial

No credit card required