FREE SHIPPING BOTH WAYS
ON EVERY ORDER!
LIST PRICE:
$118.40
Sorry, this item is currently unavailable.
Languages and Machines : An Introduction to the Theory of Computer Science
ISBN: 9780201821369 | 0201821362
Edition: 2ndFormat: Hardcover
Publisher: Addison Wesley
Pub. Date: 1/1/1997
Why Rent from Knetbooks?
Because Knetbooks knows college students. Our rental program is designed to save you time and money. Whether you need a textbook for a semester, quarter or even a summer session, we have an option for you. Simply select a rental period, enter your information and your book will be on its way!
Top 5 reasons to order all your textbooks from Knetbooks:
- We have the lowest prices on thousands of popular textbooks
- Free shipping both ways on ALL orders
- Most orders ship within 48 hours
- Need your book longer than expected? Extending your rental is simple
- Our customer support team is always here to help
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 gra... MORE
| Introduction | |
| Foundations | |
| Mathematical Preliminaries | |
| Set Theory | |
| Cartesian Product, Relations, and Functions | |
| Equivalence Relations | |
| Countable and Uncountable Sets | |
| Recursive Definitions | |
| Mathematical Induction | |
| Directed Graphs | |
| Exercises | |
| Bibliographic Note... MORE | |
| Languages | |
| Strings and Languages | |
| Finite Specification of Languages | |
| Regular Sets and Expressions | |
| Exercises | |
| Bibliographic Notes | |
| Context-Free Grammars And Parsing | |
| 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 | |
| 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 | |
| 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 | |
| Automata And Languages | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| The Chomsky Hierarchy | |
| Unrestricted Grammars | |
| Context-Sensitive Grammars | |
| Linear-Bounded Automata | |
| The Chomsky Hierarchy | |
| Exercises | |
| Bibliographic Notes | |
| Decidability And Computablity | |
| 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 | |
| Numeric Computation | |
| Computation of Functions | |
| Sequential Operation of Turing Machines | |
| Composition of Functions | |
| Toward a Programming Languages | |
| Exercises | |
| Bibliographic Notes | |
| 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 | |
| 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 | |
| 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 | |
| Deterministic Parsing | |
| 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 | |
| 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 | |
| Table of Contents provided by Publisher. All Rights Reserved. |
Related Products
Languages and Machines : An In...
Please wait while this item is added to your cart...
