## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Book Description

The Sixth Edition of An Introduction to Formal Languages and Automata provides an accessible, student-friendly presentation of all material essential to an introductory Theory of Computation course. Written to address the fundamentals of formal languages, automata, and computability, the text is 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 arguments. The author, Peter Linz, continues to offer a straightforward, uncomplicated treatment of formal languages and automata and avoids excessive mathematical detail so that students may focus on and understand the underlying principles.

1. Cover Page
2. Title Page
4. Contents
5. Preface
6. Chapter 1: Introduction to the Theory of Computation
1. 1.1 Mathematical Preliminaries and Notation
2. 1.2 Three Basic Concepts
3. 1.3 Some Applications*
7. Chapter 2: Finite Automata
1. 2.1 Deterministic Finite Accepters
2. 2.2 Nondeterministic Finite Accepters
3. 2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters
4. 2.4 Reduction of the Number of States in Finite Automata*
8. Chapter 3: Regular Languages and Regular Grammars
1. 3.1 Regular Expressions
2. 3.2 Connection Between Regular Expressions and Regular Languages
3. 3.3 Regular Grammars
9. Chapter 4: Properties of Regular Languages
1. 4.1 Closure Properties of Regular Languages
2. 4.2 Elementary Questions about Regular Languages
3. 4.3 Identifying Nonregular Languages
10. Chapter 5: Context-Free Languages
1. 5.1 Context-Free Grammars
2. 5.2 Parsing and Ambiguity
3. 5.3 Context-Free Grammars and Programming Languages
11. Chapter 6: Simplification of Context-Free Grammars and Normal Forms
1. 6.1 Methods for Transforming Grammars
2. 6.2 Two Important Normal Forms
3. 6.3 A Membership Algorithm for Context-Free Grammars*
12. Chapter 7: Pushdown Automata
1. 7.1 Nondeterministic Pushdown Automata
2. 7.2 Pushdown Automata and Context-Free Languages
3. 7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages
4. 7.4 Grammars for Deterministic Context-Free Languages*
13. Chapter 8: Properties of Context-Free Languages
1. 8.1 Two Pumping Lemmas
2. 8.2 Closure Properties and Decision Algorithms for Context-Free Languages
14. Chapter 9: Turing Machines
1. 9.1 The Standard Turing Machine
2. 9.2 Combining Turing Machines for Complicated Tasks
3. 9.3 Turing’s Thesis
15. Chapter 10: Other Models of Turing Machines
1. 10.1 Minor Variations on the Turing Machine Theme
2. 10.2 Turing Machines with More Complex Storage
3. 10.3 Nondeterministic Turing Machines
4. 10.4 A Universal Turing Machine
5. 10.5 Linear Bounded Automata
16. Chapter 11: A Hierarchy of Formal Languages and Automata
1. 11.1 Recursive and Recursively Enumerable Languages
2. 11.2 Unrestricted Grammars
3. 11.3 Context-Sensitive Grammars and Languages
4. 11.4 The Chomsky Hierarchy
17. Chapter 12: Limits of Algorithmic Computation
1. 12.1 Some Problems That Cannot Be Solved by Turing Machines
2. 12.2 Undecidable Problems for Recursively Enumerable Languages
3. 12.3 The Post Correspondence Problem
4. 12.4 Undecidable Problems for Context-Free Languages
5. 12.5 A Question of Efficiency
18. Chapter 13: Other Models of Computation
1. 13.1 Recursive Functions
2. 13.2 Post Systems
3. 13.3 Rewriting Systems
19. Chapter 14: An Overview of Computational Complexity
20. Appendix A: Finite-State Transducers
21. Appendix B: Jflap: A Useful Tool
22. Answers Solutions and Hints for Selected Exercises