Automata and Formal Languages: An Introduction

About

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.

Description

Written with the beginning user in mind. This book builds mathematical sophistication through an example rich presentation.

Sample Content

Table of Contents

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.

Updates

Submit Errata