An Introduction to Formal Languages and Automata

Front Cover
Jones & Bartlett Learning, 2001 - Computers - 410 pages
Formal languages, automata, computability, and related matters form the major part of the theory of computation. This textbook is designed for an introductory course for computer science and computer engineering majors who have knowledge of some higher-level programming language, the fundamentals of
 

Contents

Introduction to the Theory of Computation
1
Finite Automata
35
Regular Languages and Regular Grammars
71
Properties of Regular Languages
99
ContextFree Languages
125
Simplification of ContextFree Grammars
149
Pushdown Automata
175
Properties of ContextFree Languages
205
Other Models of Turing Machines
249
A Hierarchy of Formal Languages and Automata
275
Limits of Algorithmic Computation
299
Other Models of Computation
323
An Introduction to Computational Complexity
343
Answers to Selected Exercises
357
References
405
Copyright

Turing Machines
221

Other editions - View all

Common terms and phrases

Bibliographic information