6.3 Equivalence of PDAs and CFGs..................237

6.3.1 From Grammars bo Pushdown Automata.........237

6.3.2 From PDAs to Grammars..................241

6.3.3 Exercises for Section 6.3...................245

6.4 Deterministic Pushdown Automata.................246

6.4.1 Definition of a Deterministic PDA.............247

6.4.2 Regular Languages and Deterministic PDAs.......247

6.4.3 DPDAs and Context-Free Languages...........249

6.4.4 DPDAs and Ambiguous Grammars............249

6.4.5 Exercises for Section 6.4...................251

6.5 Summary of Chapter 6........................252

6.6 References for Chapter 6.......................253

7 Properties of Context-IVee Languages 255

7.1 Normal Forms for Context-Free Grammars ............255

7.1.1 Ehminating Useless Symbols................256

7.1.2 Computing the Generating and Reachable Symbols . . . . 258

7.1.3 Eliminating e-Productions..................259

7.1.4 Ehminating Unit Productions................262

7.1.0 Chomsky Normal Form...................266

7.1.6 Exercises for Section 7.1...................269

7.2 The Pumping Lemma for Context-Free Languages........274

7.2.1 The Size of Parse Trees...................274

7-2.2 Statement of the Pumping Lemma.............275

7.2.3 Applications of the Pumping Lemma for CFLs......276

7.2.4 Exercises for Section 7.2...................280

7.3 Closure Properties of Context-Free Languages...........281

7.3.1 Substitutions.........................282

7.3.2 Applications of the Substitution Theorem.........284

7.3.3 Reversal............................285

7.3.4 Intersection With a Reguhir Language...........285

7.3.5 Inverse Homomorphism...................289

7.3.6 Exercises for Section 7.3...................291

7.4 Decision Properties of CFLs ....................293

7.4.1 Complexity of Converting Among CFGs and PDAs ... 294

7.4.2 Running Time of Conversion to Chomsky Normal Ebrm , 295

7.4.3 Testing Emptiness of CFLs.................296

7.4.4 Testing Membership in a CFL ...............298

7.4.5 Preview of Undecidable CFL Problems...........302

7.4.6 Exercises for Section 7.4...................302

7.5 Summary of Chapter 7........................303

7.6 References for Chapter 7.......................304

8 Introduction to Turing Machines 307

8.1 Problems That Computers Cannot Solve..............307

8.1.1 Programs that Print Hello, World ............308

8.1.2 The Hypothetical Hello, World Tester..........310

8.1.3 Reducing One Problem to Another.............313

8.1.4 Exercises for Section 8.1...................316

8.2 The Turing Machine.........................316

8.2.1 The Quest to Decide All Mathematical Questions.....317

8.2.2 Notation for the Turing Machine..............318

8.2.3 Instantaneous Descriptions for Turing Machines......320

8.2.4 Transition Diagrams for Turing Machines.........323

8.2.-5 The Language of a Turing Macliine.............326

8.2.6 Turing Machines and Halting................327

8.2.7 Exercises for Section 8.2...................328

8.3 Programming Techniques for Turing Ma<Jiines...........329

8.3.1 Storage in the State.....................330

8.3.2 Multiple Tracks........................331

8.3.3 Subroutines..........................333

8.3.4 Exercises for Section 8.3...................334

8.4 Extensions to the Basic Turing Machine..............336

8.4.1 Multitape Turing Machines.................336

8.4.2 Equivalence of One-Tape and Multitape TMs.......337

8.4.3 Running Time and the Many-Tapes-to-One Construction 339

8.4.4 Nondeterministic Turing Machines.............340

8.4.5 Exercises for Section 8.4...................342

8.5 Restricted Turing Machines.....................345

8.5.1 Turing Macliines With Semi-infinite Tapes.........345

8-5.2 Multistack Machines.....................348

8.5.3 Counter Machines......................351

8.5.4 The Power of Counter Machines ..............352

8.5.5 Exercises for Section 8.5...................354

8.6 Turing Machines and Computers..................355

8.6.1 Simulating a Turing Machine by Computer........355

8.6.2 Simulating a Computer by a Turing Machine.......356

8.6.3 Comparing the Running Times of Computers and Turing Machines...........................361

8.7 Summary of Chapter 8........................363

8.8 References for Chapter 8.......................365

9 Undecidabiiity 367

9.1 A Language That Is Not Recursively Enumerable.........368

9.1.1 Enumerating the Binary Strings ..............369

9.1.2 Codes for Turing Machines.................369

9.1.3 The Diagonalization Langute...............370

9.1.4 Proof that Ld is not Recursively Enumerable.......372

9.1.5 Exercises for Section 9.1...................372

9.2 An Undecidable Problem That is RE................373

9.2.1 Recursive Languages.....................373

9.2.2 Complements of Recursive and RE languages.......374

9.2.3 The Universal Language...................377

9.2.4 Undecidability of the Universal Language.........379

9.2.5 Exercises for Section 9.2...................381

9.3 Undecidable Problems About Turing Machines..........383

9.3.1 Reductions..........................383

9.3.2 Turing Machines That Accept the Empty Language . . . 384

9.3.3 Rices Theorem and Properties of the RE Languages . . .387

9.3.4 Problems about Tbring-Machine Specifications......390

9.3.5 Exercises for Section 9.3...................390

9.4 Posts Correspondence Problem...................392

9.4.1 Definition of Posts Correspondence Problem.......392

9.4.2 The Modified PCP.....................394

9.4.3 Completion of the Proof of PCP Undecidability......397

9.4.4 Exercises for Section 9.4...................403

9.5 Other Undecidable Problems ....................403

9.5.1 Problems About Progirarns .................403

9.5.2 Undecidabihty of Ambiguity for CFGs ..........404

9.5.3 The Complement of a List Language............406

9.5.4 Exercises for Section 9.5...................409

9.6 Summary of Chapter 9........................410

9.7 References for Chapter 9.......................411

10 Intractable Problems 413

10.1 The Classes P and .VP .......................414

10.1.1 Problems Solvable in Polynomial Time...........414

10.1.2 An Example: Kruskals Algorithm.............414

10.1.3 Nondeterministic Polynomial Time.............419

10.1.4 An AfV Example: The Traveling Salesman Problem ... 419

10.1.5 PoljTiomial-Time Reductions................421

10.1.6 NP-Complete Problems...................422

10.1.7 Exercises for Section 10.1..................423

10.2 An NP-Complete Problem......................426

10.2.1 The Satisfiability Problem..................426

10.2.2 Representing SAT Instances.................427

10.2.3 NP-Completeness of the SAT Problem...........428

10.2.4 Exercises for Section 10.2..................434

10.3 A Restricted Satisfiability Problem.................435

10.3.1 Normal Forms for Boolean Expressions...........436

10.3.2 Converting Expressions to CNF...............437

10.3.3 NP-Completeness of CSAT.................440

10.3.4 NP-Completeness of 3SAT..................445

10.3.5 Exercises for Section 10.3..................446