An Introduction to Formal Languages and Automata

Jones & Bartlett Publishers, Feb 14, 2011 - Computers - 437 pages
Written to address the fundamentals of formal languages, automata, and computability, 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 every new printed copy expands this and offers exercises specific for JFLAP. (Please note, ebook version does not include the CD-ROM) Instructor Resources: -Instructor Manual -PowerPoint Lecture Outlines

What people are saying -Write a review

User Review - Flag as inappropriate

i've tried alot to find this book.
thx

User Review - Flag as inappropriate

good.......

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 Index 433 Copyright