An Introduction to Formal Languages and AutomataJones & Bartlett Learning, 2006 - 415 pages Fully Revised, The New Fourth Edition Of An Introduction To Formal Languages And Automata Provides An Accessible, Student-Friendly Presentation Of All Material Essential To An Introductory Theory Of Computation Course. The Text Was Designed To Familiarize Students With The Foundations And Principles Of Computer Science And To Strengthen The Students' Ability To Carry Out Formal And Rigorous Mathematical Arguments. In The New Fourth Edition, Author Peter Linz Has Offered A Straightforward, Uncomplicated Treatment Of Formal Languages And Automata And Avoids Excessive Mathematical Detail So That Students May Focus On And Understand The Underlying Principles. In An Effort To Further The Accessibility And Comprehension Of The Text, The Author Has Added New Illustrative Examples Throughout. |
Contents
Introduction to the Theory of Computation 133 | 1 |
Graphs and Trees | 8 |
Regular Expressions for Describing Simple Patterns | 86 |
Properties of Regular Languages | 99 |
ContextFree Languages | 125 |
Pushdown Automata | 175 |
Properties of ContextFree Languages | 205 |
A Hierarchy of Formal Languages and Automata | 275 |
ContextFree Languages | 114 |
125 | 125 |
132 | 132 |
6 | 147 |
Simplification of ContextFree Grammars and Normal | 149 |
175 | 175 |
196 | 196 |
205 | 205 |
Limits of Algorithmic Computation | 297 |
Answers | 363 |
References | 409 |
1 | 1 |
3 | 3 |
Pushdown Automata | 7 |
Finite Automata 37 | 37 |
Regular Languages and Regular Grammars | 71 |
77 | 77 |
86 | 86 |
RightLinear Grammars for Regular Languages | 93 |
Properties of Regular Languages | 99 |
5 | 107 |
213 | 213 |
9 | 220 |
Turing Machines 221 | 221 |
Other Models of Turing Machines 249 | 249 |
A Hierarchy of Formal Languages and Automata 275 | 275 |
Limits of Algorithmic Computation 297 | 297 |
Other Models of Computation 323 | 323 |
An Overview of Computational Complexity 343 | 343 |
Answers 363 | 363 |
References 409 | 409 |
| 413 | |
Common terms and phrases
accepts the language argument automaton closure complete computation configuration Consider construction context-free grammar context-sensitive control unit countable defined definition denoted derivation tree deterministic context-free language dfa's DTIME edges equivalent Exercise exists family of regular final Find following languages formal languages 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 linear bounded automaton M₁ move nondeterminism nondeterministic npda number of a's parsing PC-solution Post correspondence problem primitive recursive productions programming languages proof pumping lemma pushdown automata read-write head recursively enumerable languages regular expression regular grammar regular languages result s-grammar S₁ Section sentential form sequence Show simple simulate solution stack standard Turing machine step subset tape Theorem transition function transition graph undecidable unit-productions unrestricted grammar V₁ variable vertex w₁