Introduction to Formal Languages and Automata

Linz, Peter 저자(글)

Jones & Bartlett · 1997년 06월 01일

책 소개

작가정보

저자(글) Linz, Peter

목차

• Introduction to the Theory of Computation 1 (36)
  Mathematical Preliminaries and Notation 3 (11)
  Sets 3 (2)
  Functions and Relations 5 (2)
  Graphs and Trees 7 (2)
  Proof Techniques 9 (3)
  Exercises 12 (2)
  Three Basic Concepts 14 (15)
  Languages 14 (5)
  Grammars 19 (6)
  Automata 25 (1)
  Exercises 26 (3)
  Some Applications 29 (8)
  Exercises 33 (4)
  Finite Automata 37 (36)
  Deterministic Finite Accepters 37 (13)
  Deterministic Accepters and Transition 38 (2)
  Graphs
  Languages and Dfa's 40 (5)
  Regular Languages 45 (2)
  Exercises 47 (3)
  Nondeterministic Finite Accepters 50 (7)
  Definition of a Nondeterministic Accepter 50 (5)
  Why Nondeterminism? 55 (1)
  Exercises 56 (1)
  Equivalence of Deterministic and 57 (8)
  Nondeterministic Finite Accepters
  Exercises 64 (1)
  Reduction of the Number of States in Finite 65 (8)
  Automata
  Exercises 71 (2)
  Regular Languages and Regular Grammars 73 (28)
  Regular Expressions 73 (6)
  Formal Definition of a Regular Expression 74 (1)
  Languages Associated with Regular 74 (3)
  Expressions
  Exercises 77 (2)
  Connection Between Regular Expressions and 79 (11)
  Regular Languages
  Regular Expressions Denote Regular 80 (3)
  Languages
  Regular Expressions for Regular Languages 83 (3)
  Regular Expressions for Describing Simple 86 (2)
  Patterns
  Exercises 88 (2)
  Regular Grammars 90 (11)
  Right-and Left-Linear Grammars 91 (1)
  Right-Linear Grammars Generate Regular 92 (3)
  Languages
  Right-Linear Grammars for Regular 95 (2)
  Languages
  Equivalence Between Regular Languages and 97 (2)
  Regular Grammars
  Exercises 99 (2)
  Properties of Regular Languages 101(28)
  Closure Properties of Regular Languages 102(12)
  Closure under Simple Set Operations 102(3)
  Closure under Other Operations 105(6)
  Exercises 111(3)
  Elementary Questions About Regular Languages 114(3)
  Exercises 116(1)
  Identifying Nonregular Languages 117(12)
  Using the Pigeonhole Principle 117(1)
  A Pumping Lemma 118(7)
  Exercises 125(4)
  Context-Free Languages 129(26)
  Context-Free Grammars 130(10)
  Examples of Context-Free Languages 131(2)
  Leftmost and Rightmost Derivations 133(1)
  Derivation Trees 134(2)
  Relation Between Sentential Forms and 136(2)
  Derivation Trees
  Exercises 138(2)
  Parsing and Ambiguity 140(11)
  Parsing and Membership 140(5)
  Ambiguity in Grammars and Languages 145(5)
  Exercises 150(1)
  Context-Free Grammars and Programming 151(4)
  Languages
  Exercises 153(2)
  Simplification of Context-Free Grammars and 155(26)
  Normal Forms
  Methods for Transforming Grammars 156(15)
  A Useful Substitution Rule 156(3)
  Removing Useless Productions 159(4)
  Removing λ-Productions 163(2)
  Removing Unit-Productions 165(3)
  Exercises 168(3)
  Two Important Normal Forms 171(7)
  Chomsky Normal Form 171(4)
  Greibach Normal Form 175(1)
  Exercises 176(2)
  A Membership Algorithm for Context-Free 178(3)
  Grammars
  Exercises 180(1)
  Pushdown Automata 181(30)
  Nondeterministic Pushdown Automata 182(8)
  Definition of a Pushdown Automaton 182(3)
  The Language Accepted by a Pushdown 185(3)
  Automaton
  Exercises 188(2)
  Pushdown Automata and Context-Free Languages 190(11)
  Pushdown Automata for Context-Free 190(5)
  Languages
  Context-Free Grammars for Pushdown 195(5)
  Automata
  Exercises 200(1)
  Deterministic Pushdown Automata and 201(5)
  Deterministic Context-Free Languages
  Exercises 205(1)
  Grammars for Deterministic Context-Free 206(5)
  Languages
  Exercises 210(1)
  Properties of Context-Free Languages 211(18)
  Two Pumping Lemmas 211(8)
  A Pumping Lemma for Context-Free Languages 212(4)
  A Pumping Lemma for Linear Languages 216(2)
  Exercises 218(1)
  Closure Properties and Decision Algorithms 219(10)
  for Context-Free Languages
  Closure of Context-Free Languages 220(5)
  Some Decidable Properties of Context-Free 225(2)
  Languages
  Exercises 227(2)
  Turing Machines 229(28)
  The Standard Turing Machine 230(16)
  Definition of a Turing Machine 230(7)
  Turing Machines as Language Accepters 237(4)
  Turing Machines as Transducers 241(3)
  Exercises 244(2)
  Combining Turing Machines for Complicated 246(6)
  Tasks
  Exercises 251(1)
  Turing's Thesis 252(5)
  Exercises 256(1)
  Other Models of Turing Machines 257(28)
  Minor Variations on the Turing Machine Theme 258(9)
  Equivalence of Classes of Automata 258(2)
  Turing Machines with a Stay-Option 260(2)
  Turing Machines with Semi-Infinite Tape 262(1)
  The Off-Line Turing Machine 263(2)
  Exercises 265(2)
  Turing Machines With More Complex Storage 267(5)
  Multitape Turing Machines 267(3)
  Multidimensional Turing Machines 270(1)
  Exercises 271(1)
  Nondeterministic Turing Machines 272(4)
  Exercises 275(1)
  A Universal Turing Machine 276(5)
  Exercises 280(1)
  Linear Bounded Automata 281(4)
  Exercises 284(1)
  A Hierarchy of Formal Languages and Automata 285(26)
  Recursive and Recursively Enumerable 286(8)
  Languages
  Languages That Are Not Recursively 288(2)
  Enumerable
  A Language That Is Not Recursively 290(1)
  Enumerable
  A Language That Is Recursively Enumerable 291(2)
  But Not Recursive
  Exercises 293(1)
  Unrestricted Grammars 294(6)
  Exercises 299(1)
  Context-Sensitive Grammars and Languages 300(7)
  Context-Sensitive Languages and Linear 301(3)
  Bounded Automata
  Relation Between Recursive and 304(2)
  Context-Sensitive Languages
  Exercises 306(1)
  The Chomsky Hierarchy 307(4)
  Exercises 309(2)
  Limits of Algorithmic Computation 311(26)
  Some Problems that Cannot be Solved by 312(9)
  Turing Machines
  Computability and Decidability 312(1)
  The Turing Machine Halting Problem 313(4)
  Reducing One Undecidable Problem to 317(3)
  Another
  Exercises 320(1)
  Undecidable Problems for Recursively 321(4)
  Enumerable Languages
  Exercises 324(1)
  The Post Correspondence Problem 325(7)
  Exercises 331(1)
  Undecidable Problems for Context-Free 332(5)
  Languages
  Exercises 335(2)
  Other Models of Computation 337(2)
  Recursive Functions 339(9)
  Primitive Recursive Functions 340(4)
  Ackermann's Functions 344(1)
  μ-Recursive Functions 345(2)
  Exercises 347(1)
  Post Systems 348(4)
  Exercises 351(1)
  Rewriting Systems 352(1)
  Matrix Grammars 352(1)
  Markov Algorithms 353(2)
  L-Systems 355(1)
  Exercises 356
  An Introduction to Computational Complexity 257(115)
  Efficiency of Computation 358(3)
  Exercises 360(1)
  Turing Machines and Complexity 361(3)
  Exercises 364(1)
  Language Families and Complexity Classes 364(4)
  Exercises 368(1)
  The Complexity Classes P and NP 368(4)
  Exercises 371(1)
  References for Further Reading 372(1)
  Index 373
  

기본정보

ISBN	9780763702960 ( 076370296X )
발행(출시)일자	1997년 06월 01일
쪽수	준비중