Formal Language: A Practical Introduction

Formal Language:
A Practical Introduction

Adam Webber

ISBN 978-159028-197-0, $70.00

  

Contents

  1. Fundamentals (PDF preview)
  2. Finite Automata
  3. Closure Properties for Regular Languages
  4. Deterministic-Finite-Automata Applications (PDF preview)
  5. Nonderministic Finite Automata
  6. NFA Applications
  7. Regular Expressions (PDF preview)
  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

Appendix A: From an NFA to a Regular Expression
Appendix B: A Time-Hierarchy Theorem
Appendix C: Som NP-Hardess Proofs

Overview

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.

Back to Our Catalog