An Introduction to Formal Languages and AutomataFormal 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 |
Turing Machines | 221 |
Other editions - View all
Common terms and phrases
A-productions accepts the language argument closure computation configuration Consider construction context-free grammar control unit countable defined definition denoted derivation tree dfa's DTIME edge equivalent Example Exercise exists final Find finite accepter finite number formal G₁ give given grammar G Greibach normal form halting problem induction integers L₁ L1 and L2 labeled language accepted languages is closed leftmost length linear bounded automaton M₁ move nondeterminism nondeterministic npda number of a's parsing PC-solution Post correspondence problem Post system primitive recursive productions programming languages proof prove pumping lemma read-write head recursively enumerable languages regular expression regular grammar regular languages result S₁ Section sentential form sequence Show shown in Figure simple simulate solution stack standard Turing machine step string subset tape terminal Theorem transition function transition graph undecidable unit-productions unrestricted grammar V₁ variable vertex w₁