An Introduction to Formal Languages and Automata, 7th Edition

© VS148/Shutterstock.

CHAPTER 1INTRODUCTION TO THE THEORY OF COMPUTATION

CHAPTER SUMMARY

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 ...