This book has two major goals. The first is to help you understand and appreciate the beautiful and enduring ideas of formal language. These ideas are the birthright of all computer scientists, and they will profoundly change the way you think about computation. They are not only among the most beautiful, but also among the most useful tools in computer science. They are used to solve problems in a wide variety of practical applications, and they are especially useful for defining programming languages and for building language systems. The second purpose of this book is to help you develop a facility with these useful tools. Our code examples are in Java, but they are not particularly Java-centric and should be accessible to any programmer.
There is also a third major reason to study formal language, one that is not a primary focus of this book: to learn the techniques of mathematical proof. When you are learning about formal language, it can also be a good time to learn proof techniques, because the subject is full of theorems to practice on. But this book tries to make the beautiful and useful ideas for formal language accessible to students at all levels of mathematical interest and ability. To that end, although the book presents and discusses many simple proofs, it does not try to teach advanced proof techniques. Relatively few of the exercises pose challenging proof problems. Those planning graduate-level study of theoretical computer science would be well advised not to rely exclusively on this book for that kind of training.
Table of Contents:
1. Fundamentals
2. Finite Automata
3. Closure Properties for Regular Languages
4. Deterministic-Finite-Automata Applications
5. Nonderministic Finite Automata
6. NFA Applications
7. Regular Expressions
8. Regular Expression Applications
9. Advanced Topics in Regular Languages
10. Grammars
11. Nonregular Languages
12. Context-free Languages
13. Stack Machines
14. The Context-free Frontier
15. Stack Machine Applications
16. Turing Machines
17. Computability
18. Uncomputability
19. Cost Models
20. Deterministic Complexity Classes
21. Complexity Classes
