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.
- 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.
|Product dimensions:||6.00(w) x 1.25(h) x 9.00(d)|
Table of ContentsIntroduction.
I. FOUNDATIONS.1. Mathematical Preliminaries.
Cartesian Product, Relations, and Functions.
Countable and Uncountable Sets.
Finite Specification of Languages.
Regular Sets and Expressions.
II. CONTEXT-FREE GRAMMARS AND PARSING.
3. Context-Free Grammars.
Examples of Grammars and Languages.
Grammars and Languages Revisited.
A Context-Free Grammar for Pascal.
4. Parsing: An Introduction.
The Graph of a Grammar.
A Breadth-First Top-Down Parser.
A Depth-First Top-Down Parser.
A Shift-Reduce Parser.
5. Normal Forms.
Elimination of Chain Rules.
Chomsky Normal Form.
Removal of Direct Left Recursion.
Greibach Normal Form.
III. AUTOMATA AND LANGUAGES.
6. Finite Automata.
Deterministic Finite Automata.
State Diagrams and Examples.
Nondeterministic Finite Automata.
7. Regular Languages and Sets.
Regular Grammars & Finite Automata.
Closure Properties of Regular Languages.
A Nonregular Language.
The Pumping Lemma for Regular Languages.
8. Pushdown Automata and Context-Free Languages.
Pushdown Automaton and Context-Free Languages.
The Pumping Lemma for Context-Free Languages.
Closure Properties of Context-Free Languages.
A Two-Stack Automation.
9. Turing Machines.
Turing Machines as Language Acceptors.
Alternate Acceptance Criteria.
Nondeterministic Turing Machines.
Turing Machines as Language Enumerators.
10. The Chomsky Hierarchy.
The Chomsky Hierarchy.
IV. DECIDABILITY AND COMPUTABLITY.
The Church-Turing Thesis.
The Halting Problem for Turing Machines.
A Universal Machine.
An Unsolvable Word Problem.
The Post Correspondence Problem.
Undecidable Problems in Context- Free Grammars.
12. Numeric Computation.
Sequential Operation of Turing Machines.
Composition of Functions.
Toward a Programming Languages.
13. Mu-Recursive Functions.
Some Primitive Recursive Functions.
Gödel Numbering and Course-of-Values Recursion.
Computable Partial Functions.
Turing Computability and Mu-Recursive Functions.
The Church-Turing Thesis Revisited.
V. COMPUTATIONAL COMPLEXITY.
14. Computational Complexity.
Rates of Growth.
Complexity and Turing Machine Variations.
Variations of Time Complexity.
15. Tractability and NP-Complete Problems.
The Class NP.
The Satisfiability Problem.
Additional NP-Complete Problems.
Derivative Complexity Classes.
VI. DETERMINISTIC PARSING.
16. LL (k) 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.
17. LR(k) Grammars.
Acceptance by the LR(0) Machine.
Acceptance by the LR(p) Machine.
Most Helpful Customer Reviews
[A review of the 3RD EDITION, 2005.] Sudkamp gives a formal and rigorous explanation of what constitutes a language. Where this is deliberately taken to include both natural (spoken) languages and programming languages. To do this, you should note that the treatment is necessarily non-trivial. It is not a lightweight book, conceptually. The book summarises decades of work in this field, that have attempted to reduce human languages to a form that could be 'understood' by a machine. So he explains the various techniques that have arisen. Like finite state machines (finite automata). Notably, he discusses what is a Turing machine. A universal computing engine, that all other computers can map to. Such a Turing machine might be deterministic or non-deterministic. You can learn very powerful unifying ideas. From the construct of a Turing machine, the book uses this to delve into problems that are NP complete or P complete. The implementation of a solution as steps to be done by a Turing machine are elegant, and show how such a machine, while an idealisation, can be used to give provable results.