Models of Computation and Formal Languages - Bookswagon UAE
Book 1
Book 2
Book 3
Book 1
Book 2
Book 3
Book 1
Book 2
Book 3
Book 1
Book 2
Book 3
Home > Computing and Information Technology > Computer science > Mathematical theory of computation > Models of Computation and Formal Languages
Models of Computation and Formal Languages

Models of Computation and Formal Languages


     0     
5
4
3
2
1



Out of Stock


Notify me when this book is in stock
X
About the Book

Models of Computation and Formal Languages presents a comprehensive and rigorous treatment of the theory of computability. The text takes a novel approach focusing on computational models and is the first book of its kind to feature companion software. Deus Ex Machina, developed by Nicolae Savoiu, comprises software simulations of the various computational models considered and incorporates numerous examples in a user-friendly format. Part I of the text introduces several universal models including Turing machines, Markov algorithms, and register machines. Complexity theory is integrated gradually, starting in Chapter 1. The vector machine model of parallel computation is covered thoroughly both in text and software. Part II develops the Chomsky hierarchy of formal languages and provides both a grammar-theoretic and an automata-theoretic characterization of each language family. Applications to programming languages round out an in-depth theoretical discussion, making this an ideal text for students approaching this subject for the first time. Ancillary sections of several chapters relate classical computability theory to the philosophy of mind, cognitive science, and theoretical linguistics. Ideal for Theory of Computability and Theory of Algorithms courses at the advanced undergraduate or beginning graduate level, Models of Computation and Formal Languages is one of the only texts that... · · Features accompanying software available on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp/ Adopts an integrated approach to complexity theory · Offers a solutions manual containing full solutions to several hundred exercises. Most of these solutions are available to students on the World Wide Web at http://home.manhattan.edu/~gregory.taylor/thcomp · Features examples relating the theory of computation to the probable programming experience of an undergraduate computer science major

Table of Contents:
Preface 0.: Mathematical Preliminaries .1: Sets and Set-Forming Operations .2: Introduction to Formal Language Theory .3: Mappings and Functions .4: Defining Functions Recursively .5: The Mathematics of Big-O Notation .6: Mathematical Induction .7: Graphs .8: Introduction to Propositional Logic .9: Two Important Proof Techniques .10: Defining Sets Recursively .11: Infinite Sets .12: Conjunctive Normal Form .13: Number-Theoretic Predicates .14: Further Reading Part I MODELS OF COMPUTATION 1 .: Turing Machines 1.1: What Is Computation? 1.2: An Informal Description of Turing Machines 1.3: The Formal Definition of Turing Machines 1.4: Turing Machines as Language Acceptors and as Language Recognizers 1.5: Turing Machines as Computers of Number-Theoretic Functions 1.6: Modular Construction of Turing Machines 1.7: Introduction to Complexity Theory 1.8: Suggestions for Further Reading 2: Additional Varieties of Turing Machines 2.1: Turing Machines with One-Way-Infinite Tape 2.2: Turing Machines that Accept by Terminal Stare 2.3: Multitape Turing Machines 2.4: Encoding of Turing Machines 2.5: Universal Turing Machines 2.6: Nondeterministic Turing Machines 2.7: A Number-Theoretic FUnction That Is Not Turing-Computable 2.8: Turing Machines and Artificial Intelligence 2.9: Turing Machines and Cognitive Science 2.10: Regarding Theoretical Computer Science and Number-Theoretic Functions 2.11: Further Reading 3: An Introduction to Recursion Theory 3.1: The Primitive Recursive Functions 3.2: Primitive Recursive Predicates 3.3: The Partial Recursive Functions 3.4: The Class of Partial Recursive Functions Is Identical to the Class of Turing-Computable Functions 3.5: Recursive Sets 3.6: Recursively Enumerable Sets 3.7: Historical Remarks and Suggestions for Further Reading 4: Markov Algorithms 4.1: An Alternative Model of Sequential Computation 4.2: Markov Algorithms as Language Acceptors and as Language Recognizers 4.3: Markov Algorithms as Computers of Number-Theoretic Functions 4.4: Labeled Markov Algorithms 4.5: The Class of Markov-Computable Functions Is Identical to the Class of Partial Recursive Functions 4.6: Considerations of Efficiency 4.7: Computation Theory and the Foundations of Mathematics 4.8: Bibliography 5: Register Machines 5.1: Register Machines 5.2: The Class of Register-Machine-Computable Functions Is Identical to the Class of Partial Recursive Functions 5.3: Register Machines and Formal Languages 5.4: A Model-Independent Characterization of Computational Feasibility 5.5: Final Remarks and Suggestions for Further Reading 6: Post Systems (Optional) 6.1: Post Systems and Formal Languages 6.2: The Class of Post-Computable Functions Is Identical to the Class of Partial Recursive Functions 6.3: Closure Properties of the Class of Languages Generated by Post Systems 6.4: The Class of Languages Generated by Post Systems Is Identical to the Class of Turing-Acceptable Languages 6.5: Language Recognition and Post Systems 6.6: What Is a Model of Computation? 7.: The Vector Machine Model of Parallel Computation (Optional) 7.1: What Is Parallel Computation? 7.2: Vectors and Vector Operations 7.3: Vector Machines 7.4: Vector Machines and Function Computation 7.5: Vector Machines and Formal Languages 7.6: Parallel Computation and Cognitive Science 7.7: Further Remarks 8.: The Bounds of Computability 8.1: The Church-Turing Thesis 8.2: The Bounds of Computability-in-Principle: The Self-Halting Problem for Turing Machines 8.3: The Bounds of Computability-in-Principle: The Halting Problem for Turing Machines 8.4: The Bounds of Computability-in-Principle: Rice's Theorem 8.5: The Bounds of Feasible Computation: The Concept of NP-Completeness 8.6: An NP-Complete Problem (Cook-Levin Theorem) 8.7: Other NP-Complete Problems 8.8: The Bounds of Parallel Computation: The Concept of P-Completeness (Advanced) 8.9: A P-Complete Problem (Ladner's Theorem) (Advanced) 8.10: The Nearest-Neighbor Traveling Salesman Problem is P-Complete (Advanced) 8.11: Beyond Symbol Processing: The Connectionist Model of Cognition 8.12: Summary, Historical Remarks, and Suggestions for Further Reading Part II FORMAL LANGUAGES AND AUTOMATA9.: Regular Languages and Finite-State Automata 9.1: Regular Expressions and Regular Languages 9.2: Deterministic Finite-State Automata 9.3: Nondeterministic Finite-State Automata 9.4: A Pumping Lemma for FSA-Acceptable Languages 9.5: Closure Properties of the Family of FSA-Acceptable Languages 9.6: The Family of Regular Languages Is Identical to the Family of FSA-Acceptable Languages 9.7: Finite-State Automata with Epsilon-Moves 9.8: Generative Grammars 9.9: Right-Linear Grammars and Regular Languages 9.10: Summary, Historical Remarks and Suggestions for Further Reading 10.: Context-Free Languages and Pushdown-Stack Automata 10.1: Context-Free Grammars and Natural Languages 10.2: Normal Forms for Context-Free Grammars 10.3: Pushdown-Stack Automata 10.4: An Equivalent Notion of Word Acceptance for Pushdown-Stack Automata 10.5: The Class of Context-Free Languages Is Identical to the Class of PSA-Acceptable Languages 10.6: Closure Properties of the Family of Context-Free Languages 10.7: A Pumping Lemma for Context-Free Languages 10.8: Deterministic Context-Free Languages 10.9: Decidability Results for Context-Free Languages 10.10: Bibliography and Suggestions for Further Reading 11.: Context-Sensitive Languages and Linear-Bounded Automata 11.1: Context-Sensitive Grammars 11.2: A Normal Form for Context-Sensitive Grammars 11.3: Linear-Bounded Automata 11.4: Context-Sensitive Languages and Linear-Bounded Automata 11.5: Closure Properties of the Family of Context-Sensitive Languages 11.6: The General Word Problem for Context-Sensitive Languages Is Solvable 11.7: There Exist Turing-Recognizable Languages That Are Not Context-Sensitive 11.8: Final Remarks 12.: Generative Grammars and the Chomsky Hierarchy 12.1: Turing Machines and Phrase-Structure Languages 12.2: Closure Properties of the Family of Phrase-Structure Languages 12.3: Turing Machiens as Language Enumerators 12.4: A Recursion-Theoretic Characterization of the Family of Phrase-Structure Languages 12.5: The General Word Problem for Phrase-Structure Languages Is Unsolvable 12.6: The Post Correspondence Problem 12.7: The Chomsky Hierachy Epilogue Bibliography Index

About the Author :
R. Gregory Taylor holds degrees from the University of Michigan, New York University, and Columbia University. He is currently chair of the Department of Computer Science at Jersey City State College.


Best Sellers


Product Details
  • ISBN-13: 9780195109832
  • Publisher: Oxford University Press Inc
  • Publisher Imprint: Oxford University Press Inc
  • Language: English
  • Weight: 1360 gr
  • ISBN-10: 019510983X
  • Publisher Date: 02 Oct 1997
  • Binding: Hardback
  • No of Pages: 686


Similar Products

Add Photo
Add Photo

Customer Reviews

REVIEWS      0     
Click Here To Be The First to Review this Product
Models of Computation and Formal Languages
Oxford University Press Inc -
Models of Computation and Formal Languages
Writing guidlines
We want to publish your review, so please:
  • keep your review on the product. Review's that defame author's character will be rejected.
  • Keep your review focused on the product.
  • Avoid writing about customer service. contact us instead if you have issue requiring immediate attention.
  • Refrain from mentioning competitors or the specific price you paid for the product.
  • Do not include any personally identifiable information, such as full names.

Models of Computation and Formal Languages

Required fields are marked with *

Review Title*
Review
    Add Photo Add up to 6 photos
    Would you recommend this product to a friend?
    Tag this Book Read more
    Does your review contain spoilers?
    What type of reader best describes you?
    I agree to the terms & conditions
    You may receive emails regarding this submission. Any emails will include the ability to opt-out of future communications.

    CUSTOMER RATINGS AND REVIEWS AND QUESTIONS AND ANSWERS TERMS OF USE

    These Terms of Use govern your conduct associated with the Customer Ratings and Reviews and/or Questions and Answers service offered by Bookswagon (the "CRR Service").


    By submitting any content to Bookswagon, you guarantee that:
    • You are the sole author and owner of the intellectual property rights in the content;
    • All "moral rights" that you may have in such content have been voluntarily waived by you;
    • All content that you post is accurate;
    • You are at least 13 years old;
    • Use of the content you supply does not violate these Terms of Use and will not cause injury to any person or entity.
    You further agree that you may not submit any content:
    • That is known by you to be false, inaccurate or misleading;
    • That infringes any third party's copyright, patent, trademark, trade secret or other proprietary rights or rights of publicity or privacy;
    • That violates any law, statute, ordinance or regulation (including, but not limited to, those governing, consumer protection, unfair competition, anti-discrimination or false advertising);
    • That is, or may reasonably be considered to be, defamatory, libelous, hateful, racially or religiously biased or offensive, unlawfully threatening or unlawfully harassing to any individual, partnership or corporation;
    • For which you were compensated or granted any consideration by any unapproved third party;
    • That includes any information that references other websites, addresses, email addresses, contact information or phone numbers;
    • That contains any computer viruses, worms or other potentially damaging computer programs or files.
    You agree to indemnify and hold Bookswagon (and its officers, directors, agents, subsidiaries, joint ventures, employees and third-party service providers, including but not limited to Bazaarvoice, Inc.), harmless from all claims, demands, and damages (actual and consequential) of every kind and nature, known and unknown including reasonable attorneys' fees, arising out of a breach of your representations and warranties set forth above, or your violation of any law or the rights of a third party.


    For any content that you submit, you grant Bookswagon a perpetual, irrevocable, royalty-free, transferable right and license to use, copy, modify, delete in its entirety, adapt, publish, translate, create derivative works from and/or sell, transfer, and/or distribute such content and/or incorporate such content into any form, medium or technology throughout the world without compensation to you. Additionally,  Bookswagon may transfer or share any personal information that you submit with its third-party service providers, including but not limited to Bazaarvoice, Inc. in accordance with  Privacy Policy


    All content that you submit may be used at Bookswagon's sole discretion. Bookswagon reserves the right to change, condense, withhold publication, remove or delete any content on Bookswagon's website that Bookswagon deems, in its sole discretion, to violate the content guidelines or any other provision of these Terms of Use.  Bookswagon does not guarantee that you will have any recourse through Bookswagon to edit or delete any content you have submitted. Ratings and written comments are generally posted within two to four business days. However, Bookswagon reserves the right to remove or to refuse to post any submission to the extent authorized by law. You acknowledge that you, not Bookswagon, are responsible for the contents of your submission. None of the content that you submit shall be subject to any obligation of confidence on the part of Bookswagon, its agents, subsidiaries, affiliates, partners or third party service providers (including but not limited to Bazaarvoice, Inc.)and their respective directors, officers and employees.

    Accept

    Fresh on the Shelf


    Inspired by your browsing history


    Your review has been submitted!

    You've already reviewed this product!