Automata and Formal Languages: An Introduction

Automata and Formal Languages: An Introduction, 1/e

Dean Kelley, Gustavus Adolphus College

Published January, 1998 by Prentice Hall Engineering/Science/Mathematics

See other books about:
Theory of Computation/CS Theory-Computer Science

Automata Theory-Computer Science

Summary

This introduction to Automata and formal languages is designed specifically to be accessible to students with minimal mathematical background.

Features

provides a chapter-length review of the prerequisite mathematical preliminaries.
begins with an initially low level of mathematics that increases in rigor as the text proceeds — but avoids mathematically rigorous demonstrations where possible in favor of precisely stated theorems and definitions, and arguments that are motivational rather than mathematically complete or elegant.
includes a broad range of exercises that range from easy to challenging.

0. Mathematical Preliminaries.
1. Alphabets and Languages.
2. Regular Languages.
3. Context Free Languages.
4. Turing Machines.
5. Turing Machines and Languages.
6. Decidability.
7. An Introduction to Computational Complexity.
Bibliography.