An Introduction to Formal Languages and Automata

An Introduction to Formal Languages and Automata, provides an excellent presentation of the material that is essential to an introductory theory of computation course. The text was designed to familiarize students with the foundations and principles of computer science and to strengthen the students' ability to carry out formal and rigorous mathematical argument. Employing a problem-solving approach, the text provides students insight into the course material by stressing intuitive motivation and illustration of ideas through straightforward explanations and solid mathematical proofs. By emphasizing a learning through problem solving, students learn the material primarily through problem-type illustrative examples that show the motivation behind the concepts, as well as their connection to the theorems and definitions.

Key features

• New to this Edition! Text includes solved exercises providing models for students to follow as they work through the exercises.
• New to this Edition! A new two-color design!
• A problem-solving approach to learning and straightforward explanations of complicated concepts ensure that students will not become overwhelmed by the course material.
• Many carefully chosen examples are repeated in several contexts, which enables students to build an understanding through comparative study.
• Succinct topic coverage allows the book to be covered in a one-semester course.

Contents

Preface
Introduction

Chapter 1. Introduction to the Theory of Computation
Chapter 2. Finite Automata
Chapter 3. Regular Languages and Regular Games
Chapter 4. Properties of Regular Languages
Chapter 5. Context-Free Language
Chapter 6. Simplification of Context-Free Grammars and Normal Forms
Chapter 7. Pushdown Automata
Chapter 8. Properties of Context-Free Languages
Chapter 9. Turning Machines
Chapter 10. Other Modes of Turning Machines
Chapter 11. A Hierarchy of Formal Languages and Automata
Chapter 12. Limits of Algorithmic Computation
Chapter 13. Other Models of Computation
Chapter 14. An Introduction of Computational Complexity

Appendices
Solutions
Glossary
Index