|

My Instructor Resource Center :  Log in or request access

Languages and Machines: An Introduction to the Theory of Computer Science, 2/E
Thomas A. Sudkamp, Wright State University

ISBN-10: 0201821362
ISBN-13:  9780201821369

Publisher:  Addison-Wesley
Copyright:  1997
Format:  Cloth; 500 pp
Published:  11/04/1996
We're sorry, this product is no longer available and has been replaced with Languages and Machines: An Introduction to the Theory of Computer Science, 3/E.

Please contact your Pearson rep if you are using this product and need instructor resources.

Languages and Machines, which is intended for computer scientists in the theoretical foundations of their subject, gives a mathematically sound presentation of the theory of computing at the junior and senior level. Topics covered include the theory of formal languages and automata, computability, computational complexity, and deterministic parsing of context-free languages. To make these topics accessible to the undergraduate, no special mathematical prerequisites are assumed. The author examines the languages of the Chomsky hierarchy, the grammars that generate them, and the finite automata that accept them. The development of abstract machines continues with the Church-Turing thesis and computability theory. Computational complexity and NP-completeness are introduced by analyzing the computations of Turing machines. Parsing with LL and LR grammars is included to emphasize language definition and to provide the groundwork for the study of compiler design. The second edition now includes new sections covering equivalence relations, Rice's Theorem, pumping lemma for context-free grammars, the DFA minimization algorithm, and over 150 new exercises and examples.



Introduction.

I. FOUNDATIONS.

1. Mathematical Preliminaries.

Set Theory.

Cartesian Product, Relations, and Functions.

Equivalence Relations.

Countable and Uncountable Sets.

Recursive Definitions.

Mathematical Induction.

Directed Graphs.

Exercises.

Bibliographic Notes.

2. Languages.

Strings and Languages.

Finite Specification of Languages.

Regular Sets and Expressions.

Exercises.

Bibliographic Notes.

II. CONTEXT-FREE GRAMMARS AND PARSING.

3. Context-Free Grammars.

Context-Free Grammars and Languages.

Examples of Grammars and Languages.

Regular Grammars.

Grammars and Languages Revisited.

A Context-Free Grammar for Pascal.

Arithmetic Expressions.

Exercises.

Bibliographic Notes.

4. Parsing: An Introduction.

Leftmost Derivations and Ambiguity.

The Graph of a Grammar.

A Breadth-First Top-Down Parser.

A Depth-First Top-Down Parser.

Bottom-Up Parsing.

A Shift-Reduce Parser.

Exercises.

Bibliographic Notes.

5. Normal Forms.

Elimination of Lambda Rules.

Elimination of Chain Rules.

Useless Symbols.

Chomsky Normal Form.

Removal of Direct Left Recursion.

Greibach Normal Form.

Exercises.

Bibliographic Notes.

III. AUTOMATA AND LANGUAGES.

6. Finite Automata.

A Finite-State Machine.

Deterministic Finite Automata.

State Diagrams and Examples.

Nondeterministic Finite Automata.

Lambda Transitions.

Removing Nondeterminism.

DFA Minimization.

Exercises.

Bibliographic Notes.

7. Regular Languages and Sets.

Finite Automata and Regular Sets.

Expression Graphs.

Regular Grammars & Finite Automata.

Closure Properties of Regular Languages.

A Nonregular Language.

The Pumping Lemma for Regular Languages.

Myhill-Nerode Theorem.

Exercises.

Bibliographic Notes.

8. Pushdown Automata and Context-Free Languages.

Variations on the PDA Theme.

Pushdown Automaton and Context-Free Languages.

The Pumping Lemma for Context-Free Languages.

Closure Properties of Context-Free Languages.

A Two-Stack Automation.

Exercises.

Bibliographic Notes.

9. Turing Machines.

The Standard Turing Machine.

Turing Machines as Language Acceptors.

Alternate Acceptance Criteria.

Multitrack Machines.

Two-Way Tape.

Multitape Machines.

Nondeterministic Turing Machines.

Turing Machines as Language Enumerators.

Exercises.

Bibliographic Notes.

10. The Chomsky Hierarchy.

Unrestricted Grammars.

Context-Sensitive Grammars.

Linear-Bounded Automata.

The Chomsky Hierarchy.

Exercises.

Bibliographic Notes.

IV. DECIDABILITY AND COMPUTABLITY.

11. Decidability.

Decision Problems.

The Church-Turing Thesis.

The Halting Problem for Turing Machines.

A Universal Machine.

Reducibility.

Rice's Theorem.

An Unsolvable Word Problem.

The Post Correspondence Problem.

Undecidable Problems in Context- Free Grammars.

Exercises.

Bibliographic Notes.

12. Numeric Computation.

Computation of Functions.

Sequential Operation of Turing Machines.

Composition of Functions.

Toward a Programming Languages.

Exercises.

Bibliographic Notes.

13. Mu-Recursive Functions.

Primitive Recursive Functions.

Some Primitive Recursive Functions.

Bounded Operators.

Division Functions.

Gödel Numbering and Course-of-Values Recursion.

Computable Partial Functions.

Turing Computability and Mu-Recursive Functions.

The Church-Turing Thesis Revisited.

Exercises.

Bibliographic Notes.

V. COMPUTATIONAL COMPLEXITY.

14. Computational Complexity.

Time Complexity of a Turing Machine.

Linear Speed-Up.

Rates of Growth.

Complexity and Turing Machine Variations.

Variations of Time Complexity.

Nondeterministic Complexity.

Space Complexity.

Exercises.

Bibliographic Notes.

15. Tractability and NP-Complete Problems.

Tractable and Intractable Decision Problems.

The Class NP.

P=NP.

The Satisfiability Problem.

Additional NP-Complete Problems.

Derivative Complexity Classes.

Exercises.

Bibliographic Notes.

VI. DETERMINISTIC PARSING.

16. LL (k) Grammars.

Lookahead in Context-Free Grammars.

FIRST, FOLLOW, and Lookahead Sets.

Strong LL (k) Grammars.

Construction of FIRSTk Sets.

Construction of FOLLOWk Sets.

A Strong LL(1) Grammar.

A Strong LL(k) Parser.

LL(k) Grammars.

Exercises.

Bibliographic Notes.

17. LR(k) Grammars.

LR(0) Contexts.

LR(0) Parser.

LR(0) Machine.

Acceptance by the LR(0) Machine.

Acceptance by the LR(p) Machine.

LR(1) Grammars.

Exercises.

Bibliographic Notes. 0201821362T04062001

About Thomas Sudkamp

Thomas A. Sudkamp holds a Ph.D. in mathematics from the University of Notre Dame and worked extensively in industry and for the Air Force before joining the faculty at Wright State University where he has taught for over 10 years.



0201821362AB04062001

Languages and Machines gives a mathematically sound presentation of the theory of computing at the junior and senior level and is an invaluable tool for scientists investigating the theoretical foundations of computer science. Topics covered include the theory of formal languages and automata, computability, computational complexity, and deterministic parsing of context-free languages.

No special mathematical prerequisites are assumed; the theoretical concepts and associated mathematics are made accessible by a 'learn as you go' approach that develops an intuitive understanding of the concepts through numerous examples and illustrations. Languages & Machines examines the languages of the Chomsky hierarchy, the grammars that generate them, and the finite automata that accept them. Sections on the Church-Turing thesis and computability theory further examine the development of abstract machines. Computational complexity and NP-completeness are introduced by analyzing the computations of Turing machines. Parsing with LL and LR grammars is included to emphasize language definition and to provide the groundwork for the study of compiler design.

Features
  • A winning writing style, Languages and Machines is becoming recognized as an instructor's boon
  • Effective examples that convey challenging and complex theoretical concepts
  • Numerous diagrams illustrating pictorially the underlying concepts
  • Step-by-step, unhurried proofs
  • A "learn as you go" approach that develops mathematical sophistication
Features New to this Edition:
  • DFA minimization
  • Rice's Theorem
  • Increased coverage of computational complexity
  • Additional examples throughout
  • Over 150 additional exercises

** Instructor's materials are available from your sales rep. If you do not know your local sales representative, please call 1-800-552-2499 for assistance, or use the Addison Wesley Longman rep-locator at http://hepg.awl.com/rep-locator.



0201821362B04062001

Figures, 2/E
Sudkamp
©1997 | Addison-Wesley | On-line Supplement | Instock
ISBN-10: 0321314409 | ISBN-13: 9780321314406


Solutions Manual, 2/E
Sudkamp
©1997 | Addison-Wesley | On-line Supplement | Instock
ISBN-10: 0321314417 | ISBN-13: 9780321314413
    View Downloadable Files

Log in to the Instructor Resource Center

Login name: 

  Password: 

Forgot login/password?  |  Need to redeem an access code?

         

Instructor Resource Center File Download

This work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from this site should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.

Cancel                       I accept, proceed with download

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.

Copyright © Pearson Education, All rights reserved. Legal Notice | Privacy Policy | Permissions