An Introduction to Formal Languages and AutomataJones & Bartlett Publishers, 2012 - 437 pages Written to address the fundamentals of formal languages, automata, and computabilty, An Introduction to Formal Languages and Automata provides an accessible, student-friendly presentation of all material essential to an introductory Theory of Computation course. It is 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 Fifth Edition, Peter Linz continues to offer 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 and exercises throughout. There is a substantial amount of new material in the form of two new appendices, and a CD-ROM of JFLAP exercises authored by Susan Rodger of Duke University. The first appendix is an entire chapter on finite-state transducers. This optional chapter can be used to prepare students for further related study. The second appendix offers a brief introduction to JFLAP; an interactive software tool that is of great help in both learning the material and in teaching the course. Many of the exercises in the text require creating structures that are complicated and that have to be tested for correctness. JFLAP can greatly reduce students’ time spent on testing as well as help them visualize abstract concepts. The CD-ROM that accompanies this fifth edition expands this and offers exercises specific for JFLAP. |
Contents
Introduction to the Theory of Computation | 1 |
11 Mathematical Preliminaries and Notation | 3 |
12 Three Basic Concepts | 16 |
13 Some Applications | 30 |
Finite Automata | 37 |
21 Deterministic Finite Accepters | 38 |
22 Nondeterministic Finite Accepters | 49 |
23 Equivalence of Deterministic and Nondeterministic Finite Accepters | 56 |
103 Nondeterministic Turing Machines | 264 |
104 A Universal Turing Machine | 268 |
105 Linear Bounded Automata | 273 |
A Hierarchy of Formal Languages and Automata | 277 |
111 Recursive and Recursively Enumerable Languages | 278 |
112 Unrestricted Grammars | 284 |
113 ContextSensitive Grammars and Languages | 291 |
114 The Chomsky Hierarchy | 296 |
24 Reduction of the Number of States in Finite Automata | 63 |
Regular Languages and Regular Grammars | 71 |
32 Connection Between Regular Expressions and Regular Languages | 77 |
33 Regular Grammars | 89 |
Properties of Regular Languages | 99 |
41 Closure Properties of Regular Languages | 100 |
42 Elementary Questions about Regular Languages | 111 |
43 Identifying Nonregular Languages | 114 |
ContextFree Languages | 125 |
51 ContextFree Grammars | 126 |
52 Parsing and Ambiguity | 136 |
53 ContextFree Grammars and Programming Languages | 146 |
Simplification of ContextFree Grammars and Normal Forms | 149 |
61 Methods for Transforming Grammars | 150 |
62 Two Important Normal Forms | 164 |
63 A Membership Algorithm for ContextFree Grammars | 171 |
Pushdown Automata | 175 |
71 Nondeterministic Pushdown Automata | 176 |
72 Pushdown Automata and ContextFree Languages | 185 |
73 Deterministic Pushdown Automata and Deterministic ContextFree Languages | 196 |
74 Grammars for Deterministic ContextFree Languages | 201 |
Properties of ContextFree Languages | 205 |
82 Closure Properties and Decision Algorithms for ContextFree Languages | 214 |
Turing Machines | 223 |
91 The Standard Turing Machine | 224 |
92 Combining Turing Machines for Complicated Tasks | 240 |
93 Turings Thesis | 245 |
Other Models of Turing Machines | 251 |
101 Minor Variations on the Turing Machine Theme | 252 |
102 Turing Machines with More Complex Storage | 260 |
Limits of Algorithmic Computation | 299 |
121 Some Problems That Cannot Be Solved by Turing Machines | 300 |
122 Undecidable Problems for Recursively Enumerable Languages | 308 |
123 The Post Correspondence Problem | 311 |
124 Undecidable Problems for ContextFree Languages | 318 |
125 A Question of Efficiency | 322 |
Other Models of Computation | 325 |
131 Recursive Functions | 327 |
132 Post Systems | 335 |
133 Rewriting Systems | 339 |
An Overview of Computational Complexity | 345 |
141 Efficiency of Computation | 346 |
142 Turing Machine Models and Complexity | 348 |
143 Language Families and Complexity Classes | 351 |
144 The Complexity Classes P and NP | 355 |
145 Some NP Problems | 356 |
146 PolynomialTime Reduction | 360 |
147 NPCompleteness and an Open Question | 362 |
Appendix A FiniteState Transducers | 365 |
A2 Mealy Machines | 366 |
A3 Moore Machines | 368 |
A4 Moore and Mealy Machine Equivalence | 370 |
A5 Mealy Machine Minimization | 374 |
A6 Moore Machine Minimization | 378 |
A7 Limitations of FiniteState Transducers | 380 |
A Recommendation | 383 |
Answers Solutions and Hints for Selected Exercises | 385 |
References for Further Reading | 431 |
433 | |
Common terms and phrases
accepts algorithm answer applied argument associated assume automata automaton called Chapter claim complete computation Consider construction contains context-free grammar context-free languages corresponding decidable defined definition denoted derivation described determine deterministic discussion edge element equivalent Example Exercise exists Figure final Find finite first formal function give given grammar G graph halt head induction initial input integers introduce labeled length linear look move nondeterministic normal form npda operations positive possible problem productions programming proof properties prove pumping question reason recursively enumerable regular expression regular languages removed replaced represented requires restricted result rules sentential form sequence Show shown simple simulate solution stack standard starting step string Suppose symbol tape terminal Theorem transition tree true Turing machine variable write