An Introduction to Formal Languages and Automata

Front Cover
Jones & Bartlett Publishers, Feb 14, 2011 - Computers - 437 pages
3 Reviews
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

Other editions - View all

Common terms and phrases

Bibliographic information