CHAPTER 1
INTRODUCTION 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 encounter some simple examples of the role these concepts play in computer science, particularly in programming languages, digital ...
Get An Introduction to Formal Languages and Automata, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
