Preface

Contents

Index

Glossary

Models

Rogues

Table of Contents

1. The Theory of Computing
           

2. A Simple Computing Model: the Finite State Automaton and Regular Languages
           

3. Extending the Computing Model with a Stack: Pushdown Automata and Context Free Languages
           

4. Allowing Writing to the Tape in Restricted Ways: Linear Bounded Automata and Context Sensitive Languages
           

5. The Most Powerful Computing Model: Turing Machines, Algorithms, and Phrase Structure Languages
           

6. The Limits of Computing: Computability and Intractability