An introduction to formal languages and automata Peter Linz,
Publisher: Sudbury, Mass. : Jones and Bartlett Publishers, c2006.
ISBN: 0763737984
DDC: 5.131
LCC: QA267.3
Edition: (casebound)
Notes:
Includes bibliographical references (p. 409) and index.
Introduction to the Theory of Computation -- Mathematical
Preliminaries and Notation -- Three Basic Concepts -- Some
Applications -- Finite Automata: Deterministic Finite Accepters --
Nondeterministic Finite Accepters -- Equivalence of Deterministic and
Nondeterministic Finite Accepters -- Reduction of the Number of
States in Finite Automata -- Regular Languages and Regular Grammars:
Regular Expressions -- Connection Between Regular Expressions and
Regular Languages -- Regular Grammars -- Properties of Regular
Languages: Closure Properties of Regular Languages -- Elementary
Questions about Regular Languages -- Identifying Nonregular Languages
-- Context-Free Languages: Context-Free Grammars -- Parsing and
Ambiguity -- Context-Free Grammars and Programming Languages --
Simplification of Context-Free Grammars and Normal Forms: Methods for
Transforming Grammas -- Two Important Normal Forms -- A Membership
Algorithm for Context-Free Grammars* -- Pushdown Automata:
Nondeterministic Pushdown Automata -- Pushdown Automata and
Context-Free Languages -- Deterministic Pushdown Automata and
Deterministic -- Grammars for Deterministic Context-Free Languages*
-- Properties of Context-Free Languages: Two Pumping Lemmas --
Closure Properties and Decision Algorithms for Context-Free Languages
-- Turing Machines: The Standard Turing Machine -- Combining Turing
Machines for Complicated Tasks -- Turing's Thesis -- Other Models of
Turing Machines: Minor Variations on the Turing Machine Theme --
Turing Machines with More Complex Storage -- Nondeterministic Turing
Machines -- A Universal Turing Machine -- Linear Bounded Automata --
A Hierarchy of Formal Languages And Automata: Recursive and
Recursively Enumerkble Languages -- Unrestricted Grammars --
Context-Sensitive Grammars and Languages -- The Chomsky Hierarchy --
Limits of Algorithmic Computation: Some Problems That Cannot Be
Solved by Turing Machines -- Undecidable Problems for Recursively
Enumerable Languages -- The Post Correspondence Problem --
Undecidable Problems for Context-Free Languages -- A Question of
Efficiency -- Other Models of Computation: Recursive Functions --
Post Systems -- Rewriting Systems -- An Overview of Computational
Complexity: Efficiency of Computation -- Turing Machine Models and
Complexity -- Language Families and Complexity Classes -- The
Complexity Classes P and NP -- Some NP Problems -- Polynomial-Time
Reduction -- NP-Completeness and an Open Question.
Click on a subject to see other books listed with the same
subject or to drill down into components of the subject -- such as
geographical locations, dates and so on.
We query many merchants so that you can instantly
compare prices and
availability. You can even check historic prices and subscribe
for notifications. For a manual check, clicking on a link will open a
new window with a search for this book on the merchant's site of your
choice.
