形式語言與自動機導論

內(nèi)容概要

本書主要介紹形式語言、自動機、可計算性和相關內(nèi)容。主要內(nèi)容包括：計算理論導引、有窮自動機、正則語言與正則文法、上下文無關語言及文法、下推自動機、圖錄機、形式語言和自動機的層次結(jié)構(gòu)、計算復雜性等。每節(jié)后面都給出了習題，并包含部分習題的解答，方便教學。    本書是理論計算機科學方面的優(yōu)秀教材之珂作為高等院校計算機專業(yè)的教材，也可作為計算機系統(tǒng)研發(fā)人員的參考書。

作者簡介

Peter Linz 在威斯康星大學獲得博士學位，是加州大學戴維斯分校計算機科學系退休教授，其研究領域為計算機數(shù)值分析理論。除本書外，他還撰有《Exploring Numerical Methods:Fan Introduction to Scientific Computing》一書。

書籍目錄

出版者的話專家指導委員會譯者序前言第1章  計算理論導引  1.1 數(shù)學預備知識和表示  1.2 三個基本概念  1.3 一些應用第2章  有窮自動機  2.1 確定型有窮接受器  2.2 非確這型有窮接受器  2.3 確定型有窮接受器和非確定型有  2.4 減少有窮自動機中狀態(tài)的化簡第3章  正則語言與正則文法  3.1 正則表達式  3.2 正則表達和正則語言之間的聯(lián)系  3.3 正則文法第4章  正則語言的性質(zhì)  4.1 正則語言的封閉性質(zhì)  4.2 正則語言的基本問題  4.3 識別非正則語言第5章  上下文無關語言  5.1 上下文無關方法  5.2 分析和二義性  5.3 上下文無關文法和程序設計語言第6章  上下文無關文法的化簡與范式  6.1 文法變換方法  6.2 兩個重要的范式  6.3 上下文無關文法的成員資格第7章  下推自動機  7.1 非確定型下推自動機  7.2 下推自動機與上下文無關語言  7.3 確定型下推自動機和確定型上下文無關語言  7.4 確定型上下文無關語言的方法第8章  上下文無關語言的性質(zhì)  8.1 兩個泵引理  8.2 上下文無關語言的封閉性質(zhì)和判定算法第9章  圖靈機  9.1 標準圖靈機  9.2 完成復雜任務的組合圖靈機  9.3 圖靈論題第10章  圖靈機的其他模型  10.1 對圖靈機的等價性  10.2 具有更復雜存儲的圖靈機  10.3 非確定型圖靈機  10.4 通用圖靈機  10.5 線性有界自動機第11章  形式語言和自動機的層次結(jié)構(gòu)第12章  算法計算的限制第13章  其他的計算模型第14章  計算復雜性介紹部分習題的解答和提示參考文獻索引

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    形式語言與自動機導論 PDF格式下載

---