計算理論導引（原書第3版）

內容簡介

本書由計算理論領域的知名權威MichaelSipser所撰寫。他以獨特的視角，系統地介紹了計算理論的三個主要內容：自動機與語言、可計算性理論和計算複雜性理論。作者以清新的筆觸、生動的語言給出了寬泛的數學原理，而沒有拘泥於某些低層次的細節。在證明之前，均有“證明思路”，幫助讀者理解數學形式下蘊涵的概念。本書可作為計算機專業高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。

圖書目錄

Introduction to the Theory of Computation,3e

出版者的話

譯者序

第3版前言

第2版前言

第1版前言

第0章緒論

01自動機、可計算性與複雜性

011計算複雜性理論

012可計算性理論

013自動機理論

02數學概念和術語

021集合

022序列和多元組

023函式和關係

024圖

025字元串和語言

026布爾邏輯

027數學名辭彙總

03定義、定理和證明

04證明的類型

041構造性證明

042反證法

043歸納法

練習

問題

習題選解

第一部分自動機與語言

第1章正則語言

11有窮自動機

111有窮自動機的形式化定義

112有窮自動機舉例

113計算的形式化定義

114設計有窮自動機

115正則運算

12非確定性

121非確定型有窮自動機的形式化定義

122NFA與DFA的等價性

123在正則運算下的封閉性

13正則表達式

131正則表達式的形式化定義

132與有窮自動機的等價性

14非正則語言

練習

問題

習題選解

第2章上下文無關文法

21上下文無關文法概述

211上下文無關文法的形式化定義

212上下文無關文法舉例

213設計上下文無關文法

214歧義性

215喬姆斯基範式

22下推自動機

221下推自動機的形式化定義

222下推自動機舉例

223與上下文無關文法的等價性

23非上下文無關語言

24確定型上下文無關語言

241DCFL的性質

計算理論導引（原書第3版）

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條