自動(dòng)機(jī)理論與應(yīng)用

前言

This book has three goals:1. To introduce students to the elegant theory that underlies modern computing.2. To motivate students by showing them that the theory is alive. While much of it has been known since the early days of digital computers (and some of it even longer), the theory continues to inform many of the most important applications that are considered today.3. To show students how to start looking for ways to exploit the theory in their own work.The core of the book, as a standard textbook, is Parts I through V.They address the first of the stated goals. They contain the theory that is being presented. There is more ma-terial in them than can be covered in a one-semester course. Sections that are marked with a are optional, in the sense that later material does not, for the most part, de-pend on them. The Course Plans section on page xv suggests ways of selecting sections that are appropriate for some typical computer science courses.

內(nèi)容概要

本書闡述了計(jì)算科學(xué)的優(yōu)美理論基礎(chǔ)，通過演示計(jì)算理論在現(xiàn)代硬件和軟件系統(tǒng)設(shè)計(jì)中的影響，把理論知識(shí)帶到了現(xiàn)實(shí)實(shí)踐之中。本書介紹了關(guān)鍵概念的應(yīng)用，為讀者在實(shí)際工作中使用計(jì)算理論提供實(shí)際指導(dǎo)。本書討論的應(yīng)用包括：程序設(shè)計(jì)語言、編譯器、網(wǎng)絡(luò)技術(shù)、自然語言處理、人工智能、計(jì)算生物學(xué)、安全性、博弈、商業(yè)規(guī)則建模、標(biāo)識(shí)語言、Web搜索等。本書既適合作為自動(dòng)機(jī)理論課程的教程，也是相關(guān)專業(yè)人員的重要參考用書。

作者簡(jiǎn)介

作者：(美國)里奇(Rich.E.)

書籍目錄

PrefaceAcknowledgmentsCreditsPART Ⅰ INTRODUCTION  1 Why study the Theory of Computation?  2 Languages and Strings  3 The Big Picture: A Language Hierarchy  4 ComputationPART Ⅱ FINITE STATE MACHINES AND REGULAR LANGUAGES  5 Finite State Machines  6 Regular Expressions  7 Regular Grammars  8 Regular and Nonregular Languages  9 Algorithms and Decision Procedures for Regualr Languages  10 Summary and ReferencePART Ⅲ CONTEXT-FREE LANGUAGES AND PUSHDOWN AUTOMATA  11 Context-Free Grammars  12 Rushdown Automata  13 Context-Free and Noncontext-Free Languages  14 Algorithms and Decision procedures for Context-Free Languages  15 Context-Free Parsing  16 Summary and referencesPART Ⅳ TURING MACHINES AND UNDECIDABILITY  17 Turing Machines  18 The Church-Turing Thesis  19 The Church-Turing Thesis    20 Decidable and Semidecidable Languages  21 Decidability and Undecidability Proofs……PART Ⅴ COMPLEXITYAPPENDICESAPPENDICES G-Q: APPLICATIONS

章節(jié)摘錄

插圖：3.2 The Power of EncodingThe question that we are going to ask, "Is w in L？" may seem, at first glance, way toolimited to be useful. What about problems like multiplying numbers, sorting lists, andretrieving values from a database？ And what about real problems like air traffic controlor inventory management？ Can our theory tell us anything interesting about them？   The answer is yes and the key is encoding. With an appropriate encoding, otherkinds of problems can be recast as the problem of deciding whether a string is in a lan-guage. We will show some examples to illustrate this idea. We will divide the examplesinto two categories:Problems that are already stated as decision problems. For these, all we need to do   is to encode the inputs as strings and then define a language that contains exactly   the set of inputs for which the desired answer is yes.Problems that are not already stated as decision problems. These problems may   require results of any type. For these, we must first reformulate the problem as a   decision problem and then encode it as a language recognition task.

編輯推薦

《自動(dòng)機(jī)理論與應(yīng)用(影印版)》：大學(xué)計(jì)算機(jī)教育國外著名教材系列

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    自動(dòng)機(jī)理論與應(yīng)用 PDF格式下載

---