## An Introduction to Formal Languages and AutomataWritten 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 |

431 | |

433 | |

### Other editions - View all

### Common terms and phrases

A-productions accepts the language alphabet argument Chapter complete computation conﬁguration Consider construction context-free grammar countable deﬁned deﬁnition denoted derivation tree deterministic context-free language dfa’s edge equivalent Example Exercise exists ﬁnal ﬁnd ﬁrst FORMAL LANGUAGES give given grammar G Greibach normal form halting problem induction inﬁnite input symbol integers L1 and L2 labeled language accepted leftmost length linear bounded automaton Mealy machine modiﬁed Moore machine move nondeterminism nondeterministic notation npda output parsing Post correspondence problem Post system preﬁx primitive recursive productions programming languages proof pumping lemma pushdown automata read-write head recursively enumerable languages regular expression regular grammar regular languages result satisﬁes Section sentential form sequence Show shown in Figure simple simulate speciﬁc stack standard Turing machine step subset tape Theorem transducer transition function transition graph undecidable unit-productions unrestricted grammar variable vertex